{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Multiple of Three"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestMultipleOfThree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #形成三的最大倍数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>digits</code>，你可以通过按 <strong>任意顺序</strong> 连接其中某些数字来形成 <strong>3</strong> 的倍数，请你返回所能得到的最大的 3 的倍数。</p>\n",
    "\n",
    "<p>由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。如果无法得到答案，请返回一个空字符串。返回的结果不应包含不必要的前导零。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>digits = [8,1,9]\n",
    "<strong>输出：</strong>\"981\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>digits = [8,6,7,1,0]\n",
    "<strong>输出：</strong>\"8760\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>digits = [1]\n",
    "<strong>输出：</strong>\"\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>digits = [0,0,0,0,0,0]\n",
    "<strong>输出：</strong>\"0\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= digits.length &lt;= 10^4</code></li>\n",
    "\t<li><code>0 &lt;= digits[i] &lt;= 9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-multiple-of-three](https://leetcode.cn/problems/largest-multiple-of-three/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-multiple-of-three](https://leetcode.cn/problems/largest-multiple-of-three/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[8,1,9]', '[8,6,7,1,0]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(cnt, t1, t2):\n",
    "    for v in t1:\n",
    "        if cnt[v] > 0:\n",
    "            cnt[v] -= 1\n",
    "            return get_ans(cnt)\n",
    "    tmp = 2\n",
    "    for v in t2:\n",
    "        if cnt[v] >= tmp:\n",
    "            cnt[v] -= tmp\n",
    "            return get_ans(cnt)\n",
    "        tmp -= cnt[v]\t\n",
    "        cnt[v] = 0\n",
    "    return ''\n",
    "    \n",
    "def get_ans(cnt):\n",
    "    s = ''\n",
    "    for i in range(9, -1, -1):\n",
    "        s += \"{}\".format(i) * cnt[i]\n",
    "    if s and s[0] == \"0\":\n",
    "        return '0'    \n",
    "    return s\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt = [0] * 10\n",
    "        res = 0\n",
    "        for v in digits:\n",
    "            cnt[v] += 1\n",
    "            res += v\n",
    "        a = res % 3\n",
    "        if a == 0:\n",
    "            return get_ans(cnt)\n",
    "            \n",
    "        if a == 1:\n",
    "            return func1(cnt, (1, 4, 7), (2, 5, 8))\n",
    "        # a == 2\t\n",
    "        return func1(cnt, (2, 5, 8), (1, 4, 7))\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        count = [0] * 10\n",
    "        sum_nums = 0\n",
    "        for i in digits:\n",
    "            count[i] += 1\n",
    "            sum_nums += i\n",
    "        if sum_nums%3 != 0:\n",
    "            func1(sum_nums%3,count)\n",
    "        res = \"\"\n",
    "        if sum(count) != 0:\n",
    "            if count[0]>0 and sum(count[1:]) == 0:\n",
    "                return \"0\"\n",
    "            for i in range(9, -1, -1):\n",
    "                res += str(i) * count[i]\n",
    "            return res\n",
    "        return \"\"\n",
    "def func1(n,count):\n",
    "    if n == 1:\n",
    "        lst = [1,4,7]\n",
    "        k = 2\n",
    "        m = 8\n",
    "    if n == 2:\n",
    "        lst = [2,5,8]\n",
    "        k = 1\n",
    "        m = 7\n",
    "    for j in lst:\n",
    "        if count[j] > 0:\n",
    "            count[j] -= 1\n",
    "            break\n",
    "    else:\n",
    "        tmp = 2\n",
    "        while k <= m:\n",
    "            if count[k] > 0:\n",
    "                count[k] -= 1\n",
    "                tmp -= 1\n",
    "                if tmp == 0:\n",
    "                    break\n",
    "                continue\n",
    "            k += 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        count = [0] * 10\n",
    "        sum_nums = 0\n",
    "        for i in digits:\n",
    "            count[i] += 1\n",
    "            sum_nums += i\n",
    "        if sum_nums%3 != 0:\n",
    "            func1(sum_nums%3,count)\n",
    "        res = \"\"\n",
    "        if sum(count) != 0:\n",
    "            if count[0]>0 and sum(count[1:]) == 0:\n",
    "                return \"0\"\n",
    "            for i in range(9, -1, -1):\n",
    "                res += str(i) * count[i]\n",
    "            return res\n",
    "        return \"\"\n",
    "def func1(n,count):\n",
    "    if n == 1:\n",
    "        lst = [1,4,7]\n",
    "        k = 2\n",
    "        m = 8\n",
    "    if n == 2:\n",
    "        lst = [2,5,8]\n",
    "        k = 1\n",
    "        m = 7\n",
    "    for j in lst:\n",
    "        if count[j] > 0:\n",
    "            count[j] -= 1\n",
    "            break\n",
    "    else:\n",
    "        tmp = 2\n",
    "        while k <= m:\n",
    "            if count[k] > 0:\n",
    "                count[k] -= 1\n",
    "                tmp -= 1\n",
    "                if tmp == 0:\n",
    "                    break\n",
    "                continue\n",
    "            k += 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "\n",
    "        count = [0] * 10\n",
    "        sum_nums = 0\n",
    "        for i in digits:\n",
    "            count[i] += 1\n",
    "            sum_nums += i\n",
    "\n",
    "        if sum_nums % 3 == 1:\n",
    "            for j in [1, 4, 7]:\n",
    "                if count[j] > 0:\n",
    "                    count[j] -= 1\n",
    "                    break\n",
    "            else:\n",
    "                tmp = 2\n",
    "                j = 2\n",
    "                while j <= 8:\n",
    "                    if count[j] > 0:\n",
    "                        count[j] -= 1\n",
    "                        tmp -= 1\n",
    "                        if tmp == 0:\n",
    "                            break\n",
    "                        continue\n",
    "                    j += 3\n",
    "        elif sum_nums % 3 == 2:\n",
    "\n",
    "            for j in [2, 5, 8]:\n",
    "                if count[j] > 0:\n",
    "                    count[j] -= 1\n",
    "                    break\n",
    "            else:\n",
    "                tmp = 2\n",
    "                j = 1\n",
    "                while j <= 7:\n",
    "                    if count[j] > 0:\n",
    "                        count[j] -= 1\n",
    "                        tmp -= 1\n",
    "                        if tmp == 0:\n",
    "                            break\n",
    "                        continue\n",
    "                    j += 3\n",
    "        res = \"\"\n",
    "        print(count)\n",
    "        if sum(count) != 0:\n",
    "            if count[0]>0 and sum(count[1:]) == 0:\n",
    "                return \"0\"\n",
    "            for i in range(9, -1, -1):\n",
    "                res += str(i) * count[i]\n",
    "            return res\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt, modulo = [0] * 10, [0] * 3\n",
    "        s = 0\n",
    "        for digit in digits:\n",
    "            cnt[digit] += 1\n",
    "            modulo[digit % 3] += 1\n",
    "            s += digit\n",
    "        \n",
    "        remove_mod, rest = 0, 0\n",
    "        if s % 3 == 1:\n",
    "            remove_mod, rest = (1, 1) if modulo[1] >= 1 else (2, 2)\n",
    "        elif s % 3 == 2:\n",
    "            remove_mod, rest = (2, 1) if modulo[2] >= 1 else (1, 2)\n",
    "\n",
    "        ans = \"\"\n",
    "        for i in range(0, 10):\n",
    "            for j in range(cnt[i]):\n",
    "                if rest > 0 and remove_mod == i % 3:\n",
    "                    rest -= 1\n",
    "                else:\n",
    "                    ans += str(i)\n",
    "        if len(ans) > 0 and ans[-1] == \"0\":\n",
    "            ans = \"0\"\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(cnt, t1, t2):\n",
    "    for v in t1:\n",
    "        if cnt[v] > 0:\n",
    "            cnt[v] -= 1\n",
    "            return get_ans(cnt)\n",
    "    tmp = 2\n",
    "    for v in t2:\n",
    "        if cnt[v] >= tmp:\n",
    "            cnt[v] -= tmp\n",
    "            return get_ans(cnt)\n",
    "        tmp -= cnt[v]\t\n",
    "        cnt[v] = 0\n",
    "    return ''\n",
    "    \n",
    "def get_ans(cnt):\n",
    "    s = ''\n",
    "    for i in range(9, -1, -1):\n",
    "        s += \"{}\".format(i) * cnt[i]\n",
    "    if s and s[0] == \"0\":\n",
    "        return '0'    \n",
    "    return s\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt = [0] * 10\n",
    "        res = 0\n",
    "        for v in digits:\n",
    "            cnt[v] += 1\n",
    "            res += v\n",
    "        a = res % 3\n",
    "        if a == 0:\n",
    "            return get_ans(cnt)\n",
    "            \n",
    "        if a == 1:\n",
    "            return func1(cnt, (1, 4, 7), (2, 5, 8))\n",
    "        # a == 2\t\n",
    "        return func1(cnt, (2, 5, 8), (1, 4, 7))\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        count = [0] * 10\n",
    "        sum_num = sum(digits)\n",
    "        \n",
    "        for num in digits:\n",
    "            count[num] += 1\n",
    "        s = str()\n",
    "        for i in range(1, 11):\n",
    "            if count[-i] != 0:\n",
    "                s += str(10 - i) * count[-i]\n",
    "                \n",
    "        if sum_num % 3 == 0:\n",
    "            if sum_num == 0:\n",
    "                return \"0\"\n",
    "            return s\n",
    "        if sum_num % 3 == 1:\n",
    "            for v in [1, 4, 7]:\n",
    "                if count[v] > 0:\n",
    "                    count[v] -= 1\n",
    "                    s1 = str()\n",
    "                    \n",
    "                    for k in range(1, 11):\n",
    "                        \n",
    "                        if count[-k] != 0:\n",
    "                            s1 += str(10 - k) * count[-k]\n",
    "                    \n",
    "                    if sum(count) > 0:\n",
    "                        if count[0] != 0 and sum(count[1:]) == 0:\n",
    "                            return \"0\"\n",
    "                    return s1\n",
    "            for i in [2, 5, 8]:\n",
    "                if count[i] > 0:\n",
    "                    count[i] -= 1\n",
    "                    for j in [2,5,8]:\n",
    "                        if count[j] > 0:\n",
    "                            count[j] -= 1\n",
    "                            s1 = str()\n",
    "                            for k in range(1, 11):\n",
    "                                if count[-k] != 0:\n",
    "                                    s1 += str(10 - k) * count[-k]\n",
    "                                    \n",
    "                            if sum(count) > 0:\n",
    "                                if count[0] != 0 and sum(count[1:]) == 0:\n",
    "                                    return \"0\"\n",
    "                            return s1\n",
    "            return \"\"\n",
    "        for v in [2, 5, 8]:\n",
    "            if count[v] > 0:\n",
    "                count[v] -= 1\n",
    "                s1 = str()\n",
    "                for k in range(1, 11):\n",
    "                    if count[-k] != 0:\n",
    "                        s1 += str(10 - k) * count[-k]\n",
    "                if sum(count) > 0:\n",
    "                    if count[0] != 0 and sum(count[1:]) == 0:\n",
    "                        return \"0\"\n",
    "                return s1\n",
    "        for i in [1, 4, 7]:\n",
    "            if count[i] > 0:\n",
    "                count[i] -= 1\n",
    "                for j in [1, 4, 7]:\n",
    "                    if count[j] > 0:\n",
    "                        count[j] -= 1\n",
    "                        s1 = str()\n",
    "                        for k in range(1, 11):\n",
    "                            if count[-k] != 0:\n",
    "                                s1 += str(10 - k) * count[-k]\n",
    "                        if sum(count) > 0:\n",
    "                            if count[0] != 0 and sum(count[1:]) == 0:\n",
    "                                return \"0\"\n",
    "                        return s1\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt = [0] * 10\n",
    "        s = sum(digits)\n",
    "        ans = ''\n",
    "        for x in digits:\n",
    "            cnt[x] += 1\n",
    "\n",
    "        def f(y: int) -> bool:\n",
    "            for i in range(y, 10, 3):\n",
    "                if cnt[i]:\n",
    "                    cnt[i] -= 1\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "        \n",
    "        if s % 3 == 1:\n",
    "            if not f(1):\n",
    "                f(2)\n",
    "                f(2)\n",
    "        elif s % 3 == 2:\n",
    "            if not f(2):\n",
    "                f(1)\n",
    "                f(1)\n",
    "\n",
    "        for i in range(9, -1, -1):\n",
    "            while cnt[i]:\n",
    "                ans += str(i)\n",
    "                cnt[i] -= 1\n",
    "            \n",
    "        if ans and ans[0] == '0':\n",
    "            return '0'\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt, modulo = [0] * 10, [0] * 3\n",
    "        s = 0\n",
    "        for digit in digits:\n",
    "            cnt[digit] += 1\n",
    "            modulo[digit % 3] += 1\n",
    "            s += digit\n",
    "        \n",
    "        remove_mod, rest = 0, 0\n",
    "        if s % 3 == 1:\n",
    "            remove_mod, rest = (1, 1) if modulo[1] >= 1 else (2, 2)\n",
    "        elif s % 3 == 2:\n",
    "            remove_mod, rest = (2, 1) if modulo[2] >= 1 else (1, 2)\n",
    "\n",
    "        ans = \"\"\n",
    "        for i in range(0, 10):\n",
    "            for j in range(cnt[i]):\n",
    "                if rest > 0 and remove_mod == i % 3:\n",
    "                    rest -= 1\n",
    "                else:\n",
    "                    ans += str(i)\n",
    "        if len(ans) > 0 and ans[-1] == \"0\":\n",
    "            ans = \"0\"\n",
    "        return ans[::-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(count):\n",
    "    s = \"\"\n",
    "    for i in range(1, 11):\n",
    "        if count[-i] != 0:\n",
    "            s += str(10 - i) * count[-i]\n",
    "    return s\n",
    "def func2(count,k):\n",
    "    if k == 1:\n",
    "        lst1 = [1,4,7]\n",
    "        lst2 = [2, 5, 8]\n",
    "    else:\n",
    "        lst2 = [1,4,7]\n",
    "        lst1 = [2, 5, 8]\n",
    "    for v in lst1:\n",
    "        if count[v] > 0:\n",
    "            count[v] -= 1\n",
    "            s1 = func1(count)\n",
    "            if sum(count) > 0:\n",
    "                if count[0] != 0 and sum(count[1:]) == 0:\n",
    "                    return \"0\"\n",
    "            return s1\n",
    "    for i in lst2:\n",
    "        if count[i] > 0:\n",
    "            count[i] -= 1\n",
    "            for j in lst2:\n",
    "                if count[j] > 0:\n",
    "                    count[j] -= 1\n",
    "                    s1 = func1(count)\n",
    "                    if sum(count) > 0:\n",
    "                        if count[0] != 0 and sum(count[1:]) == 0:\n",
    "                            return \"0\"\n",
    "                    return s1\n",
    "    return \"\"\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        count = [0] * 10\n",
    "        sum_num = sum(digits)\n",
    "        if sum_num == 0:\n",
    "            return \"0\"\n",
    "        for num in digits:\n",
    "            count[num] += 1\n",
    "        if sum_num % 3 == 0:\n",
    "            return func1(count)\n",
    "        if sum_num % 3 == 1:\n",
    "            return func2(count,k = 1)\n",
    "        return func2(count,k = 2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(count):\n",
    "    s = \"\"\n",
    "    for i in range(1, 11):\n",
    "        if count[-i] != 0:\n",
    "            s += str(10 - i) * count[-i]\n",
    "    return s\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        count = [0] * 10\n",
    "        sum_num = sum(digits)\n",
    "        if sum_num == 0:\n",
    "            return \"0\"\n",
    "        for num in digits:\n",
    "            count[num] += 1\n",
    "        if sum_num % 3 == 0:\n",
    "            return func1(count)\n",
    "        if sum_num % 3 == 1:\n",
    "            for v in [1, 4, 7]:\n",
    "                if count[v] > 0:\n",
    "                    count[v] -= 1\n",
    "                    s1 = func1(count)\n",
    "                    if sum(count) > 0:\n",
    "                        if count[0] != 0 and sum(count[1:]) == 0:\n",
    "                            return \"0\"\n",
    "                    return s1\n",
    "            for i in [2, 5, 8]:\n",
    "                if count[i] > 0:\n",
    "                    count[i] -= 1\n",
    "                    for j in [2,5,8]:\n",
    "                        if count[j] > 0:\n",
    "                            count[j] -= 1\n",
    "                            s1 = func1(count)\n",
    "                            if sum(count) > 0:\n",
    "                                if count[0] != 0 and sum(count[1:]) == 0:\n",
    "                                    return \"0\"\n",
    "                            return s1\n",
    "            return \"\"\n",
    "        for v in [2, 5, 8]:\n",
    "            if count[v] > 0:\n",
    "                count[v] -= 1\n",
    "                s1 = func1(count)\n",
    "                if sum(count) > 0:\n",
    "                    if count[0] != 0 and sum(count[1:]) == 0:\n",
    "                        return \"0\"\n",
    "                return s1\n",
    "        for i in [1, 4, 7]:\n",
    "            if count[i] > 0:\n",
    "                count[i] -= 1\n",
    "                for j in [1, 4, 7]:\n",
    "                    if count[j] > 0:\n",
    "                        count[j] -= 1\n",
    "                        s1 = func1(count)\n",
    "                        if sum(count) > 0:\n",
    "                            if count[0] != 0 and sum(count[1:]) == 0:\n",
    "                                return \"0\"\n",
    "                        return s1\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt, modulo = [0] * 10, [0] * 3\n",
    "        s = 0\n",
    "        for digit in digits:\n",
    "            cnt[digit] += 1\n",
    "            modulo[digit % 3] += 1\n",
    "            s += digit\n",
    "        \n",
    "        remove_mod, rest = 0, 0\n",
    "        if s % 3 == 1:\n",
    "            remove_mod, rest = (1, 1) if modulo[1] >= 1 else (2, 2)\n",
    "        elif s % 3 == 2:\n",
    "            remove_mod, rest = (2, 1) if modulo[2] >= 1 else (1, 2)\n",
    "\n",
    "        ans = \"\"\n",
    "        for i in range(0, 10):\n",
    "            for j in range(cnt[i]):\n",
    "                if rest > 0 and remove_mod == i % 3:\n",
    "                    rest -= 1\n",
    "                else:\n",
    "                    ans += str(i)\n",
    "        if len(ans) > 0 and ans[-1] == \"0\":\n",
    "            ans = \"0\"\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func147(lst):\n",
    "    for i in range(1, 10, 3):\n",
    "        if lst[i] >= 1:\n",
    "            lst[i] -= 1\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "\n",
    "def func258(lst):\n",
    "    for i in range(2, 10, 3):\n",
    "        if lst[i] >= 1:\n",
    "            lst[i] -= 1\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "\n",
    "def get_result(lst):\n",
    "    s = ''\n",
    "    for i in range(9, -1, -1):\n",
    "        s += lst[i] * str(i)\n",
    "    if not s:\n",
    "        return s\n",
    "    if s == '0'*len(s):\n",
    "        return '0'\n",
    "    return s\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        lst = [0] * 10\n",
    "        sum_ = 0\n",
    "        for v in digits:\n",
    "            sum_ += v\n",
    "            lst[v] += 1\n",
    "        if sum_ == 0:\n",
    "            return '0'\n",
    "\n",
    "        if sum_ % 3 == 0:\n",
    "            return get_result(lst)\n",
    "\n",
    "        if sum_ % 3 == 1:\n",
    "            tmp = func147(lst)\n",
    "            if tmp:\n",
    "                return get_result(lst)\n",
    "            tmp1 = func258(lst)\n",
    "            tmp2 = func258(lst)\n",
    "            if not tmp1 or not tmp2:\n",
    "                return ''\n",
    "            return get_result(lst)\n",
    "\n",
    "        if sum_ % 3 == 2:\n",
    "            tmp = func258(lst)\n",
    "            if tmp:\n",
    "                return get_result(lst)\n",
    "            tmp1 = func147(lst)\n",
    "            tmp2 = func147(lst)\n",
    "            if not tmp1 or not tmp2:\n",
    "                return ''\n",
    "            return get_result(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt, mod = [0] * 10, [0] * 3\n",
    "        s = 0\n",
    "        for x in digits:\n",
    "            cnt[x] += 1\n",
    "            mod[x%3] += 1\n",
    "            s += x\n",
    "        remove, rest = 0, 0\n",
    "        if s % 3 == 1:\n",
    "            remove, rest = (1, 1) if mod[1] >= 1 else (2, 2)\n",
    "        elif s % 3 == 2:\n",
    "            remove, rest = (2, 1) if mod[2] >= 1 else (1, 2)\n",
    "\n",
    "        ans = \"\"\n",
    "        for i in range(10):\n",
    "            for j in range(cnt[i]):\n",
    "                if rest > 0 and remove == i % 3:\n",
    "                    rest -= 1\n",
    "                else:\n",
    "                    ans += str(i)\n",
    "        if len(ans) > 0 and ans[-1] == \"0\":\n",
    "            ans = \"0\"\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_res(t, tn, cnt):\n",
    "\twhile t < 10:\n",
    "\t\twhile cnt[t]:\n",
    "\t\t\tcnt[t] -= 1\n",
    "\t\t\ttn -= 1\n",
    "\t\t\tif not tn:\n",
    "\t\t\t\treturn True\n",
    "\t\tt += 3\n",
    "\treturn False\n",
    "\n",
    "def out(cnt):\n",
    "\tres = ''\n",
    "\tfor i, v in enumerate(cnt):\n",
    "\t\tres = str(i) * v + res\n",
    "\tif set(res) == {'0'}:\n",
    "\t\treturn '0'\n",
    "\treturn res\n",
    "\n",
    "def main(digits):\n",
    "\tcnt = [0] * 10\n",
    "\tsum_all = 0\n",
    "\tfor v in digits:\n",
    "\t\tcnt[v] += 1\n",
    "\t\tsum_all += v\n",
    "\t\n",
    "\ta = sum_all % 3\n",
    "\n",
    "\tif a == 1:\n",
    "\t\tif get_res(1, 1, cnt) or get_res(2, 2, cnt):\n",
    "\t\t\treturn out(cnt)\n",
    "\t\treturn ''\n",
    "\n",
    "\tif a == 2:\n",
    "\t\tif get_res(2, 1, cnt) or get_res(1, 2, cnt):\n",
    "\t\t\treturn out(cnt)\n",
    "\t\treturn ''\n",
    "\t\t\n",
    "\treturn out(cnt)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        return main(digits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        freq = [0] * 10\n",
    "        for d in digits:\n",
    "            freq[d] += 1\n",
    "        s = 0\n",
    "        for i in range(10):\n",
    "            s += freq[i] * i\n",
    "        target = s % 3\n",
    "        #要删掉这么多 0 1 2\n",
    "        #print(target)\n",
    "        if target == 0:\n",
    "            return self.construct(freq)\n",
    "        elif target == 1:\n",
    "            cand = [1, 4, 7]\n",
    "            #能否用一个数构成余1 不能的话，看看有没有两个余2的\n",
    "            for i in cand:\n",
    "                if freq[i] > 0:\n",
    "                    freq[i] -= 1\n",
    "                    return self.construct(freq)\n",
    "            cand = [2, 5, 8]\n",
    "            left = 2\n",
    "            for i in cand:\n",
    "                if freq[i] >= left:\n",
    "                    freq[i] -= left\n",
    "                    return self.construct(freq)\n",
    "                elif freq[i] > 0:\n",
    "                    freq[i] -= 1\n",
    "                    left = 1\n",
    "            return ''\n",
    "        elif target == 2:\n",
    "            cand = [2, 5, 8]\n",
    "            for i in cand:\n",
    "                if freq[i] > 0:\n",
    "                    freq[i] -= 1\n",
    "                    return self.construct(freq)\n",
    "            cand = [1, 4, 7]\n",
    "            left = 2\n",
    "            for i in cand:\n",
    "                if freq[i] >= left:\n",
    "                    freq[i] -= left\n",
    "                    return self.construct(freq)\n",
    "                elif freq[i] > 0:\n",
    "                    freq[i] -= 1\n",
    "                    left = 1\n",
    "            return ''\n",
    "        return\n",
    "\n",
    "    def construct(self, freq):\n",
    "        if sum(freq) == 0:\n",
    "            return ''\n",
    "        elif sum(freq[1:]) == 0:\n",
    "            return '0'\n",
    "        else:\n",
    "            s = ''\n",
    "            for i in range(9, -1, -1):\n",
    "                s += str(i) * freq[i]\n",
    "            return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(count):\n",
    "    s = \"\"\n",
    "    for i in range(1, 11):\n",
    "        if count[-i] != 0:\n",
    "            s += str(10 - i) * count[-i]\n",
    "    return s\n",
    "def func2(count):\n",
    "    lst1 = [1,4,7]\n",
    "    for v in [1, 4, 7]:\n",
    "        if count[v] > 0:\n",
    "            count[v] -= 1\n",
    "            s1 = func1(count)\n",
    "            if sum(count) > 0:\n",
    "                if count[0] != 0 and sum(count[1:]) == 0:\n",
    "                    return \"0\"\n",
    "            return s1\n",
    "    for i in [2, 5, 8]:\n",
    "        if count[i] > 0:\n",
    "            count[i] -= 1\n",
    "            for j in [2,5,8]:\n",
    "                if count[j] > 0:\n",
    "                    count[j] -= 1\n",
    "                    s1 = func1(count)\n",
    "                    if sum(count) > 0:\n",
    "                        if count[0] != 0 and sum(count[1:]) == 0:\n",
    "                            return \"0\"\n",
    "                    return s1\n",
    "    return \"\"\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        count = [0] * 10\n",
    "        sum_num = sum(digits)\n",
    "        if sum_num == 0:\n",
    "            return \"0\"\n",
    "        for num in digits:\n",
    "            count[num] += 1\n",
    "        if sum_num % 3 == 0:\n",
    "            return func1(count)\n",
    "        if sum_num % 3 == 1:\n",
    "            return func2(count)\n",
    "            \n",
    "        for v in [2, 5, 8]:\n",
    "            if count[v] > 0:\n",
    "                count[v] -= 1\n",
    "                s1 = func1(count)\n",
    "                if sum(count) > 0:\n",
    "                    if count[0] != 0 and sum(count[1:]) == 0:\n",
    "                        return \"0\"\n",
    "                return s1\n",
    "        for i in [1, 4, 7]:\n",
    "            if count[i] > 0:\n",
    "                count[i] -= 1\n",
    "                for j in [1, 4, 7]:\n",
    "                    if count[j] > 0:\n",
    "                        count[j] -= 1\n",
    "                        s1 = func1(count)\n",
    "                        if sum(count) > 0:\n",
    "                            if count[0] != 0 and sum(count[1:]) == 0:\n",
    "                                return \"0\"\n",
    "                        return s1\n",
    "        return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def func1(count):\n",
    "    s = \"\"\n",
    "    for i in range(1, 11):\n",
    "        if count[-i] != 0:\n",
    "            s += str(10 - i) * count[-i]\n",
    "    return s\n",
    "def func2(count,k):\n",
    "    if k == 1:\n",
    "        lst1 = [1,4,7]\n",
    "        lst2 = [2, 5, 8]\n",
    "    else:\n",
    "        lst2 = [1,4,7]\n",
    "        lst1 = [2, 5, 8]\n",
    "    for v in lst1:\n",
    "        if count[v] > 0:\n",
    "            count[v] -= 1\n",
    "            s1 = func1(count)\n",
    "            if sum(count) > 0:\n",
    "                if count[0] != 0 and sum(count[1:]) == 0:\n",
    "                    return \"0\"\n",
    "            return s1\n",
    "    for i in lst2:\n",
    "        if count[i] > 0:\n",
    "            count[i] -= 1\n",
    "            for j in lst2:\n",
    "                if count[j] > 0:\n",
    "                    count[j] -= 1\n",
    "                    s1 = func1(count)\n",
    "                    if sum(count) > 0:\n",
    "                        if count[0] != 0 and sum(count[1:]) == 0:\n",
    "                            return \"0\"\n",
    "                    return s1\n",
    "    return \"\"\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        count = [0] * 10\n",
    "        sum_num = sum(digits)\n",
    "        if sum_num == 0:\n",
    "            return \"0\"\n",
    "        for num in digits:\n",
    "            count[num] += 1\n",
    "        if sum_num % 3 == 0:\n",
    "            return func1(count)\n",
    "        if sum_num % 3 == 1:\n",
    "            return func2(count,k = 1)\n",
    "        return func2(count,k = 2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def out(count):\n",
    "    res = ''\n",
    "    for i in range(len(count) - 1, -1, -1):\n",
    "        res += str(i)  * count[i]\n",
    "    if len(res)>0 and  all(c == '0' for c in res):\n",
    "        return '0'\n",
    "    return res\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        count = [0] * 10\n",
    "        sum1 = 0\n",
    "        for v in digits:\n",
    "            count[v] += 1\n",
    "            sum1 += v\n",
    "        if sum1 == 0:\n",
    "            return '0'\n",
    "\n",
    "        if sum1 % 3 == 0:\n",
    "            return out(count)\n",
    "\n",
    "        def func147():\n",
    "            for v in (1, 4, 7):\n",
    "                if count[v] == 0:\n",
    "                    continue\n",
    "                count[v] -= 1\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        def func258():\n",
    "            for v in (2, 5, 8):\n",
    "                if count[v] == 0:\n",
    "                    continue\n",
    "                count[v] -= 1\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        if sum1 % 3 == 1:\n",
    "            # func147()\n",
    "            if not func147():\n",
    "                func258()\n",
    "                if not func258():\n",
    "                    return ''\n",
    "\n",
    "        if sum1 % 3 == 2:\n",
    "            if not func258():\n",
    "                func147()\n",
    "                if not func147():\n",
    "                    return ''\n",
    "        return out(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_res(t, tn, cnt):\n",
    "\twhile t < 10:\n",
    "\t\twhile cnt[t]:\n",
    "\t\t\tcnt[t] -= 1\n",
    "\t\t\ttn -= 1\n",
    "\t\t\tif not tn:\n",
    "\t\t\t\treturn True\n",
    "\t\tt += 3\n",
    "\treturn False\n",
    "\n",
    "def out(cnt):\n",
    "\tres = ''\n",
    "\tfor i, v in enumerate(cnt):\n",
    "\t\tres = str(i) * v + res\n",
    "\tif set(res) == {'0'}:\n",
    "\t\treturn '0'\n",
    "\treturn res\n",
    "\n",
    "def main(digits):\n",
    "\tcnt = [0] * 10\n",
    "\tsum_all = 0\n",
    "\tfor v in digits:\n",
    "\t\tcnt[v] += 1\n",
    "\t\tsum_all += v\n",
    "\t\n",
    "\ta = sum_all % 3\n",
    "\n",
    "\tif a == 1:\n",
    "\t\tif get_res(1, 1, cnt) or get_res(2, 2, cnt):\n",
    "\t\t\treturn out(cnt)\n",
    "\t\treturn ''\n",
    "\n",
    "\tif a == 2:\n",
    "\t\tif get_res(2, 1, cnt) or get_res(1, 2, cnt):\n",
    "\t\t\treturn out(cnt)\n",
    "\t\treturn ''\n",
    "\t\t\n",
    "\treturn out(cnt)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        return main(digits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        counter = [0] * 10\n",
    "        sum_num = 0\n",
    "\n",
    "        # 统计每个数字的出现次数和总和\n",
    "        for v in digits:\n",
    "            counter[v] += 1\n",
    "            sum_num += v\n",
    "\n",
    "        # 寻找符合条件的数字组合\n",
    "        def find_numbers(nums, target):\n",
    "            for num in nums:\n",
    "                if counter[num] > 0:\n",
    "                    counter[num] -= 1\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        a = sum_num % 3\n",
    "\n",
    "        # 处理余数为1的情况\n",
    "        if a == 1:\n",
    "            if not find_numbers([1, 4, 7], 1):\n",
    "                find_numbers([2, 5, 8], 2)\n",
    "                find_numbers([2, 5, 8], 2)\n",
    "        \n",
    "        # 处理余数为2的情况\n",
    "        elif a == 2:\n",
    "            if not find_numbers([2, 5, 8], 2):\n",
    "                find_numbers([1, 4, 7], 1)\n",
    "                find_numbers([1, 4, 7], 1)\n",
    "\n",
    "        result = ''\n",
    "        # 构造结果字符串\n",
    "        for i in range(9, -1, -1):\n",
    "            result += str(i) * counter[i]\n",
    "\n",
    "        # 处理特殊情况，如果结果以'0'开头，返回'0'\n",
    "        if result and result[0] == '0':\n",
    "            return '0'\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt, modulo = [0] * 10, [0] * 3\n",
    "        s = 0\n",
    "        for digit in digits:\n",
    "            cnt[digit] += 1\n",
    "            modulo[digit % 3] += 1\n",
    "            s += digit\n",
    "        \n",
    "        remove_mod, rest = 0, 0\n",
    "        if s % 3 == 1:\n",
    "            remove_mod, rest = (1, 1) if modulo[1] >= 1 else (2, 2)\n",
    "        elif s % 3 == 2:\n",
    "            remove_mod, rest = (2, 1) if modulo[2] >= 1 else (1, 2)\n",
    "\n",
    "        ans = \"\"\n",
    "        for i in range(0, 10):\n",
    "            for j in range(cnt[i]):\n",
    "                if rest > 0 and remove_mod == i % 3:\n",
    "                    rest -= 1\n",
    "                else:\n",
    "                    ans += str(i)\n",
    "        if len(ans) > 0 and ans[-1] == \"0\":\n",
    "            ans = \"0\"\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "\n",
    "        cnt = [0]*10 \n",
    "        module = [0]*3\n",
    "        s = 0\n",
    "        for num in digits:\n",
    "            cnt[num] += 1\n",
    "            module[num % 3] += 1\n",
    "            s += num\n",
    "        \n",
    "        remove_mod, rest = 0, 0\n",
    "\n",
    "        if s % 3 == 1:\n",
    "            if module[1] >= 1:\n",
    "                remove_mod = 1\n",
    "                rest = 1\n",
    "            else:\n",
    "                remove_mod = 2\n",
    "                rest = 2\n",
    "\n",
    "        elif s % 3 == 2:\n",
    "            if module[2] >= 1:\n",
    "                remove_mod = 2\n",
    "                rest = 1\n",
    "            else:\n",
    "                remove_mod = 1\n",
    "                rest = 2\n",
    "        \n",
    "        ans = \"\"\n",
    "\n",
    "        for i in range(0, 10):\n",
    "            for j in range(cnt[i]):\n",
    "                if rest > 0 and remove_mod == i % 3:\n",
    "                    rest -= 1\n",
    "                else: \n",
    "                    ans += str(i)\n",
    "        \n",
    "        if len(ans) > 0 and ans[-1] == '0':\n",
    "            ans = \"0\"\n",
    "        \n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def out(count):\n",
    "    res = ''\n",
    "    for i in range(len(count) - 1, -1, -1):\n",
    "        res += str(i)  * count[i]\n",
    "    if not res:\n",
    "        return res\n",
    "    if all(c == '0' for c in res):\n",
    "        return '0'\n",
    "    return res\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        count = [0] * 10\n",
    "        sum1 = 0\n",
    "        for v in digits:\n",
    "            count[v] += 1\n",
    "            sum1 += v\n",
    "        if sum1 == 0:\n",
    "            return '0'\n",
    "\n",
    "        if sum1 % 3 == 0:\n",
    "            return out(count)\n",
    "\n",
    "        def func147():\n",
    "            for v in (1, 4, 7):\n",
    "                if count[v] == 0:\n",
    "                    continue\n",
    "                count[v] -= 1\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        def func258():\n",
    "            for v in (2, 5, 8):\n",
    "                if count[v] == 0:\n",
    "                    continue\n",
    "                count[v] -= 1\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        if sum1 % 3 == 1:\n",
    "            # func147()\n",
    "            if not func147():\n",
    "                func258()\n",
    "                if not func258():\n",
    "                    return ''\n",
    "\n",
    "        if sum1 % 3 == 2:\n",
    "            if not func258():\n",
    "                func147()\n",
    "                if not func147():\n",
    "                    return ''\n",
    "        return out(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt, modulo = [0] * 10, [0] * 3\n",
    "        s = 0\n",
    "        for digit in digits:\n",
    "            cnt[digit] += 1\n",
    "            modulo[digit % 3] += 1\n",
    "            s += digit\n",
    "        \n",
    "        remove_mod, rest = 0, 0\n",
    "        if s % 3 == 1:\n",
    "            remove_mod, rest = (1, 1) if modulo[1] >= 1 else (2, 2)\n",
    "        elif s % 3 == 2:\n",
    "            remove_mod, rest = (2, 1) if modulo[2] >= 1 else (1, 2)\n",
    "\n",
    "        ans = \"\"\n",
    "        for i in range(0, 10):\n",
    "            for j in range(cnt[i]):\n",
    "                if rest > 0 and remove_mod == i % 3:\n",
    "                    rest -= 1\n",
    "                else:\n",
    "                    ans += str(i)\n",
    "        if len(ans) > 0 and ans[-1] == \"0\":\n",
    "            ans = \"0\"\n",
    "        return ans[::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt, modulo = [0] * 10, [0] * 3\n",
    "        s = 0\n",
    "        for digit in digits:\n",
    "            cnt[digit] += 1\n",
    "            modulo[digit % 3] += 1\n",
    "            s += digit\n",
    "        \n",
    "        remove_mod, rest = 0, 0\n",
    "        if s % 3 == 1:\n",
    "            remove_mod, rest = (1, 1) if modulo[1] >= 1 else (2, 2)\n",
    "        elif s % 3 == 2:\n",
    "            remove_mod, rest = (2, 1) if modulo[2] >= 1 else (1, 2)\n",
    "\n",
    "        ans = \"\"\n",
    "        for i in range(0, 10):\n",
    "            for j in range(cnt[i]):\n",
    "                if rest > 0 and remove_mod == i % 3:\n",
    "                    rest -= 1\n",
    "                else:\n",
    "                    ans += str(i)\n",
    "        if len(ans) > 0 and ans[-1] == \"0\":\n",
    "            ans = \"0\"\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "\n",
    "\t\t\t\t\t\tCounter = [0]*10\n",
    "\t\t\t\t\t\tsum_num = 0\n",
    "\t\t\t\t\t\t\n",
    "\t\t\t\t\t\tfor v in digits:\n",
    "\t\t\t\t\t\t\t\tCounter[v] += 1\n",
    "\t\t\t\t\t\t\t\tsum_num += v\n",
    "\t\t\t\t\t\t\t\t\n",
    "\t\t\t\t\t\tdef func_147():\n",
    "\t\t\t\t\t\t\t\tfor v in (1, 4, 7):\n",
    "\t\t\t\t\t\t\t\t\t\tif Counter[v] == 0:\n",
    "\t\t\t\t\t\t\t\t\t\t\t\tcontinue\n",
    "\t\t\t\t\t\t\t\t\t\tCounter[v] -= 1\n",
    "\t\t\t\t\t\t\t\t\t\treturn True\n",
    "\t\t\t\t\t\t\t\treturn False\n",
    "\n",
    "\t\t\t\t\t\tdef func_258():\n",
    "\t\t\t\t\t\t\t\tfor v in (2, 5, 8):\n",
    "\t\t\t\t\t\t\t\t\t\tif Counter[v] == 0:\n",
    "\t\t\t\t\t\t\t\t\t\t\t\tcontinue\n",
    "\t\t\t\t\t\t\t\t\t\tCounter[v] -= 1\n",
    "\t\t\t\t\t\t\t\t\t\treturn True\n",
    "\t\t\t\t\t\t\t\treturn False\n",
    "\t\t\t\t\t\t\n",
    "\t\t\t\t\t\ta = sum_num % 3\n",
    "\t\t\t\t\t\t\n",
    "\t\t\t\t\t\tif a == 1:\n",
    "\t\t\t\t\t\t\t\tif not func_147():\n",
    "\t\t\t\t\t\t\t\t\t\tfunc_258()\n",
    "\t\t\t\t\t\t\t\t\t\tif not func_258():\n",
    "\t\t\t\t\t\t\t\t\t\t\t\treturn ''\n",
    "\t\t\t\t\t\t\n",
    "\t\t\t\t\t\tif a == 2:\n",
    "\t\t\t\t\t\t\t\tif not func_258():\n",
    "\t\t\t\t\t\t\t\t\t\tfunc_147()\n",
    "\t\t\t\t\t\t\t\t\t\tif not func_147():\n",
    "\t\t\t\t\t\t\t\t\t\t\t\treturn ''\n",
    "\t\t\t\t\t\t\n",
    "\t\t\t\t\t\ts = ''\n",
    "\t\t\t\t\t\tfor i in range(9, -1, -1):\n",
    "\t\t\t\t\t\t\t\ts += str(i) * Counter[i]\n",
    "\t\t\t\t\t\t\n",
    "\t\t\t\t\t\tif s and s[0] == '0':\n",
    "\t\t\t\t\t\t\t\treturn '0'\n",
    "\t\t\t\t\t\t\n",
    "\t\t\t\t\t\treturn s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt = [0] * 10\n",
    "        ans = []\n",
    "        for d in digits:\n",
    "            cnt[d] += 1\n",
    "        mod1 = cnt[1] + cnt[4] + cnt[7]\n",
    "        mod2 = cnt[2] + cnt[5] + cnt[8]\n",
    "        if mod1 == 0:\n",
    "            d = -(mod2 % 3)\n",
    "        elif mod2 == 0:\n",
    "            d = mod1 % 3\n",
    "        else:\n",
    "            mod1 %= 3\n",
    "            mod2 %= 3\n",
    "            if mod1 == mod2:\n",
    "                d = 0\n",
    "            elif (mod1, mod2) in [(1, 0), (2, 1), (0, 2)]:\n",
    "                d = 1\n",
    "            else:\n",
    "                d = -1\n",
    "\n",
    "\n",
    "        if d >= 0:\n",
    "            for i in (1, 4, 7):\n",
    "                if d <= cnt[i]:\n",
    "                    cnt[i] -= d\n",
    "                    break\n",
    "                else:\n",
    "                    d -= cnt[i]\n",
    "                    cnt[i] = 0\n",
    "        else:\n",
    "            d = -d\n",
    "            for i in (2, 5, 8):\n",
    "                if d <= cnt[i]:\n",
    "                    cnt[i] -= d\n",
    "                    break\n",
    "                else:\n",
    "                    d -= cnt[i]\n",
    "                    cnt[i] = 0\n",
    "\n",
    "        all_zero = True\n",
    "        for i in range(9, 0, -1):\n",
    "            if cnt[i]:\n",
    "                all_zero = False\n",
    "            ans.append(str(i) * cnt[i])\n",
    "\n",
    "        if all_zero:\n",
    "            return \"0\" if cnt[0] else \"\"\n",
    "        \n",
    "        ans.append(\"0\" * cnt[0])\n",
    "        return \"\".join(ans)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt, modulo = [0] * 10, [0] * 3\n",
    "        s = 0\n",
    "        for digit in digits:\n",
    "            cnt[digit] += 1\n",
    "            modulo[digit % 3] += 1\n",
    "            s += digit\n",
    "        \n",
    "        remove_mod, rest = 0, 0\n",
    "        if s % 3 == 1:\n",
    "            remove_mod, rest = (1, 1) if modulo[1] >= 1 else (2, 2)\n",
    "        elif s % 3 == 2:\n",
    "            remove_mod, rest = (2, 1) if modulo[2] >= 1 else (1, 2)\n",
    "\n",
    "        ans = \"\"\n",
    "        for i in range(0, 10):\n",
    "            for j in range(cnt[i]):\n",
    "                if rest > 0 and remove_mod == i % 3:\n",
    "                    rest -= 1\n",
    "                else:\n",
    "                    ans += str(i)\n",
    "        if len(ans) > 0 and ans[-1] == \"0\":\n",
    "            ans = \"0\"\n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt, mod = [0 for _ in range(10)], [0 for _ in range(3)]\n",
    "        for d in digits:\n",
    "            mod[d % 3] += 1\n",
    "            cnt[d] += 1\n",
    "        tot = sum(digits)\n",
    "        res = [0, 0]\n",
    "        if tot % 3 == 1:\n",
    "            if mod[1] >= 1:\n",
    "                res = [1, 1]\n",
    "            else:\n",
    "                res = [2, 2]\n",
    "        elif tot % 3 == 2:\n",
    "            if mod[2] >= 1:\n",
    "                res = [2, 1]\n",
    "            else:\n",
    "                res = [1, 2]\n",
    "        ans = ''\n",
    "        for i in range(10):\n",
    "            for _ in range(cnt[i]):\n",
    "                if i % 3 == res[0] and res[1]:\n",
    "                    res[1] -= 1\n",
    "                else:\n",
    "                    ans = f'{i}{ans}'\n",
    "        z = Counter(ans)\n",
    "        if len(z) == 1 and ans[0] == '0': ans = '0'\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        sum_i = sum(digits)\n",
    "        if sum_i == 0:\n",
    "            return \"0\"\n",
    "        digits.sort()\n",
    "        index_list = [None, []]\n",
    "        if sum_i % 3 != 0:\n",
    "            if sum_i % 3 == 1:\n",
    "                for i in range(len(digits)):\n",
    "                    if digits[i] % 3 == 1:\n",
    "                        index_list[0] = i\n",
    "                        break\n",
    "                    if digits[i] % 3 == 2 and len(index_list[1]) < 2:\n",
    "                        index_list[1].append(i)\n",
    "            if sum_i % 3 == 2:\n",
    "                for i in range(len(digits)):\n",
    "                    if digits[i] % 3 == 2:\n",
    "                        index_list[0] = i\n",
    "                        break\n",
    "                    if digits[i] % 3 == 1 and len(index_list[1]) < 2:\n",
    "                        index_list[1].append(i)\n",
    "            if index_list[0] != None:\n",
    "                digits.pop(index_list[0])\n",
    "            elif len(index_list[1]) == 2:\n",
    "                digits.pop(index_list[1][1])\n",
    "                digits.pop(index_list[1][0])\n",
    "            else:\n",
    "                return \"\"\n",
    "        if not digits:\n",
    "            return \"\"\n",
    "        result = \"\"\n",
    "        flag = False\n",
    "        for i in range(len(digits)-1, -1, -1):\n",
    "            if not flag and digits[i] == 0:\n",
    "                continue\n",
    "            flag = True\n",
    "            result += str(digits[i])\n",
    "        return result if result else \"0\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits):\n",
    "        counts = [0] * 10\n",
    "        sum = 0\n",
    "        for num in digits:\n",
    "            counts[num] += 1\n",
    "        for i in range(10):\n",
    "            sum += counts[i] * i\n",
    "     \n",
    "        a=sum%3\n",
    "        def output(counts):\n",
    "            res=''\n",
    "            for i in range(10):\n",
    "                #if res[0]!=0:\n",
    "                res =counts[i] * str(i) +res  \n",
    "            return res\n",
    "        res=output(counts)\n",
    "        if a == 0:\n",
    "            if len(res)>1 and res[:2]==\"00\":\n",
    "                return '0' \n",
    "            return res\n",
    "        \n",
    "        def func147():\n",
    "            for v in (1,4,7):\n",
    "                if counts[v]==0:\n",
    "                    continue\n",
    "                counts[v]-=1\n",
    "                return True\n",
    "            return False\n",
    "        def func258():\n",
    "            for v in (2,5,8):\n",
    "                if counts[v]==0:\n",
    "                    continue\n",
    "                counts[v]-=1\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        if a == 1:\n",
    "            if not func147():\n",
    "                func258()\n",
    "                if not func258():\n",
    "                    return ''\n",
    "        if a == 2:\n",
    "            if not func258():\n",
    "                func147()\n",
    "                if not func147():\n",
    "                    return ''\n",
    "        res=output(counts)          \n",
    "        if len(res)>1 and res[:2]==\"00\":\n",
    "            return '0' \n",
    "        return res\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        counter = [0] * 10\n",
    "        sum_num = 0\n",
    "\n",
    "        # 统计每个数字的出现次数和总和\n",
    "        for v in digits:\n",
    "            counter[v] += 1\n",
    "            sum_num += v\n",
    "\n",
    "        # 寻找符合条件的数字组合\n",
    "        def find_numbers(nums, target):\n",
    "            for num in nums:\n",
    "                if counter[num] > 0:\n",
    "                    counter[num] -= 1\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        a = sum_num % 3\n",
    "\n",
    "        # 处理余数为1的情况\n",
    "        if a == 1:\n",
    "            if not find_numbers([1, 4, 7], 1):\n",
    "                find_numbers([2, 5, 8], 2)\n",
    "                find_numbers([2, 5, 8], 2)\n",
    "        \n",
    "        # 处理余数为2的情况\n",
    "        elif a == 2:\n",
    "            if not find_numbers([2, 5, 8], 2):\n",
    "                find_numbers([1, 4, 7], 1)\n",
    "                find_numbers([1, 4, 7], 1)\n",
    "\n",
    "        result = ''\n",
    "        # 构造结果字符串\n",
    "        for i in range(9, -1, -1):\n",
    "            result += str(i) * counter[i]\n",
    "\n",
    "        # 处理特殊情况，如果结果以'0'开头，返回'0'\n",
    "        if result and result[0] == '0':\n",
    "            return '0'\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        s = 0\n",
    "        res = \"\"\n",
    "        nums, mods = [0] * 10, [0] * 3\n",
    "\n",
    "        for d in digits:\n",
    "            nums[d] += 1\n",
    "            mods[d%3] += 1\n",
    "            s = s + d\n",
    "\n",
    "        rest, mod = 0, 0\n",
    "        if s % 3 == 1:\n",
    "            rest, mod = (1, 1) if mods[1] >= 1 else (2, 2)\n",
    "        if s % 3 == 2:\n",
    "            rest, mod = (1, 2) if mods[2] >= 1 else (2, 1)\n",
    "\n",
    "        for i in range(0, 10):\n",
    "            for j in range(nums[i]):\n",
    "                if rest > 0 and i % 3 == mod:\n",
    "                    rest -= 1\n",
    "                else:\n",
    "                    res += str(i)\n",
    "\n",
    "            \n",
    "        if len(res) > 0 and res[-1] == \"0\":\n",
    "            return \"0\"\n",
    "\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt = [0] * 10\n",
    "        mod = [0] * 3\n",
    "        s = 0\n",
    "\n",
    "        for d in digits:\n",
    "            cnt[d] += 1\n",
    "            mod[d % 3] += 1\n",
    "            s += d\n",
    "        \n",
    "        del_mod, rest = 0, 0\n",
    "        if s % 3 == 1:\n",
    "            del_mod, rest = (1, 1) if mod[1] >= 1 else (2, 2)\n",
    "        elif s % 3 == 2:\n",
    "            del_mod, rest = (2, 1) if mod[2] >= 1 else (1, 2)\n",
    "        \n",
    "        ans = \"\"\n",
    "        for i in range(10):\n",
    "            for j in range(cnt[i]):\n",
    "                if rest > 0 and i % 3 == del_mod:\n",
    "                    rest -= 1\n",
    "                    continue\n",
    "                else:\n",
    "                    ans += str(i)\n",
    "        \n",
    "        if len(ans) > 0 and ans[-1] == '0':\n",
    "            return '0'\n",
    "        return ans[::-1]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        sum_i = sum(digits)\n",
    "        if sum_i == 0:\n",
    "            return \"0\"\n",
    "        digits.sort()\n",
    "        index_list = [None, []]\n",
    "        if sum_i % 3 != 0:\n",
    "            if sum_i % 3 == 1:\n",
    "                for i in range(len(digits)):\n",
    "                    if digits[i] % 3 == 1:\n",
    "                        index_list[0] = i\n",
    "                        break\n",
    "                    if digits[i] % 3 == 2 and len(index_list[1]) < 2:\n",
    "                        index_list[1].append(i)\n",
    "            if sum_i % 3 == 2:\n",
    "                for i in range(len(digits)):\n",
    "                    if digits[i] % 3 == 2:\n",
    "                        index_list[0] = i\n",
    "                        break\n",
    "                    if digits[i] % 3 == 1 and len(index_list[1]) < 2:\n",
    "                        index_list[1].append(i)\n",
    "            if index_list[0] != None:\n",
    "                digits.pop(index_list[0])\n",
    "            elif len(index_list[1]) == 2:\n",
    "                digits.pop(index_list[1][1])\n",
    "                digits.pop(index_list[1][0])\n",
    "            else:\n",
    "                return \"\"\n",
    "        if not digits:\n",
    "            return \"\"\n",
    "        result = \"\"\n",
    "        flag = False\n",
    "        for i in range(len(digits)-1, -1, -1):\n",
    "            if not flag and digits[i] == 0:\n",
    "                continue\n",
    "            flag = True\n",
    "            result += str(digits[i])\n",
    "        return result if result else \"0\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "\n",
    "        cnt = [0]*10 \n",
    "        module = [0]*3\n",
    "        s = 0\n",
    "        for num in digits:\n",
    "            cnt[num] += 1\n",
    "            module[num % 3] += 1\n",
    "            s += num\n",
    "        \n",
    "        remove_mod, rest = 0, 0\n",
    "\n",
    "        if s % 3 == 1:\n",
    "            if module[1] >= 1:\n",
    "                remove_mod = 1\n",
    "                rest = 1\n",
    "            else:\n",
    "                remove_mod = 2\n",
    "                rest = 2\n",
    "\n",
    "        elif s % 3 == 2:\n",
    "            if module[2] >= 1:\n",
    "                remove_mod = 2\n",
    "                rest = 1\n",
    "            else:\n",
    "                remove_mod = 1\n",
    "                rest = 2\n",
    "        \n",
    "        ans = \"\"\n",
    "\n",
    "        for i in range(0, 10):\n",
    "            for j in range(cnt[i]):\n",
    "                if rest > 0 and remove_mod == i % 3:\n",
    "                    rest -= 1\n",
    "                else: \n",
    "                    ans += str(i)\n",
    "        \n",
    "        if len(ans) > 0 and ans[-1] == '0':\n",
    "            ans = \"0\"\n",
    "        \n",
    "        return ans[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "# 那么对于给定的数组 digits，记数组中所有元素之和为 S，那么就有以下的三种情况：\n",
    "# 若 S 是 3 的倍数，那么选择数组 digits 中的所有元素，它们任意组成的数都能被 3 整除，因此我们只需要将其从大到小排序再连接成一个数即可；\n",
    "# 若 S 模 3 余 1，那么我们需要从数组 digits 从删除若干个元素，它们的和模 3 也余 1。为了使得最后得到的数尽可能大，最优的方法一定是从 digits 中删除一个最小的模 3 余 1 的数（例如 1，4，7）。如果 digits 中没有这样的数，我们可以退而求其次，删除两个最小的模 3 余 2 的数（例如 2，5，8）。会不会也没有这样的数呢？如果 digits 中既没有模 3 余 1 的数，也最多只有一个模 3 余 2 的数，那么 digits 中所有元素之和要么是 3 的倍数（此时没有模 3 余 2 的数），要么模 3 余 2（此时有一个模 3 余 2 的数），不可能得到模 3 余 1 的结果。因此我们一定能通过删除一个模 3 余 1 的数或者两个模 3 余 2 的数，使得 digits 中所有元素之和变为 3 的倍数。在这之后，我们同样从大到小进行排序再连接成一个数；\n",
    "# 若 S 模 3 余 2，与上面的情况类似，我们从 digits 中删除一个最小的模 3 余 2 的数，如果没有这样的数，就删除两个最小的模 3 余 1 的数。\n",
    "\n",
    "# 我们遍历数组 digits，记录下每个数字出现的次数 cnt 以及它们模 3 的结果出现的次数 modulo。在遍历的同时，我们求出所有的元素之和 S。\n",
    "# 根据 S 模 3 的结果以及 modulo 中的记录情况，我们可以得到一个二元组 (remove_mod, rest)，其中 remove_mod 表示要删除的元素模 3 余几，rest 表示删除数的个数。\n",
    "# 在这之后，我们从小到大遍历所有的数（已经以频数的形式记录在 cnt 中了，省去了排序），并根据二元组 (remove_mod, rest) 删除最小的若干个数。\n",
    "# 最后我们再从大到小遍历所有的数，并把它们连接起来作为最终的结果。需要注意的是，如果剩余的所有数都是 0，那么我们只要返回一个 0 作为答案即可。\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        nums, cnt = [0] * 10, [0] * 3\n",
    "        total = 0\n",
    "        for d in digits:\n",
    "            nums[d] += 1\n",
    "            cnt[d % 3] += 1\n",
    "            total += d\n",
    "        remove_mode, rest = 0, 0\n",
    "        if total % 3 == 1:\n",
    "            remove_mode, rest = (1, 1) if cnt[1] > 0 else (2, 2)\n",
    "        elif total % 3 == 2:\n",
    "            remove_mode, rest = (2, 1) if cnt[2] > 0 else (1, 2)\n",
    "\n",
    "        res = \"\"\n",
    "        for i in range(10):\n",
    "            for _ in range(nums[i]):\n",
    "                if rest > 0 and i % 3 == remove_mode:\n",
    "                    rest -= 1\n",
    "                else:\n",
    "                    res += str(i)\n",
    "        if len(res) > 0 and res[-1] == \"0\":\n",
    "            return \"0\"\n",
    "\n",
    "        return res[::-1]\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "#         nums, cnt = [0] * 10, [0] * 3\n",
    "#         total = 0\n",
    "#         for d in digits:\n",
    "#             nums[d] += 1\n",
    "#             cnt[d % 3] += 1\n",
    "#             total += d\n",
    "#         remove_mod, rest = 0, 0\n",
    "#         if total % 3 == 1:\n",
    "#             remove_mod, rest = (1, 1) if cnt[1] >= 1 else (2, 2)\n",
    "#         elif total % 3 == 2:\n",
    "#             remove_mod, rest = (2, 1) if cnt[2] >= 1 else (1, 2)\n",
    "#         res = \"\"\n",
    "#         for i in range(10):\n",
    "#             for _ in range(nums[i]):\n",
    "#                 if rest > 0 and i % 3 == remove_mod:\n",
    "#                     rest -= 1\n",
    "#                 else:\n",
    "#                     res += str(i)\n",
    "#         if len(res) > 0 and res[-1] == \"0\":\n",
    "#             return \"0\"\n",
    "#         return res[::-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        n = len(digits)\n",
    "        C = Counter(digits)\n",
    "        if C[0] == n:return '0'\n",
    "        s = 0\n",
    "        cnt1,cnt2 = 0,0\n",
    "        for idx,v in C.items():\n",
    "            s += int(idx)*v\n",
    "            if int(idx) % 3 == 1:cnt1 += v\n",
    "            if int(idx) % 3 == 2:cnt2 += v\n",
    "        print(C,cnt1,cnt2)    \n",
    "        res = ''\n",
    "        if s % 3 == 1:\n",
    "            if cnt1:\n",
    "                for i in 1,4,7:\n",
    "                    if C[i]:C[i] -= 1;break\n",
    "            else:\n",
    "                cccc = 2\n",
    "                for i in 2,5,8:\n",
    "                    while C[i] and cccc:\n",
    "                        C[i] -= 1\n",
    "                        cccc -= 1\n",
    "        elif s % 3 == 2:\n",
    "            if cnt2:\n",
    "                for i in 2,5,8:\n",
    "                    if C[i]:C[i] -= 1;break\n",
    "            else:\n",
    "                cccc = 2\n",
    "                for i in 1,4,7:\n",
    "                    while C[i] and cccc:\n",
    "                        C[i] -= 1\n",
    "                        cccc -= 1\n",
    "        res = ''\n",
    "        for i in range(9,-1,-1):\n",
    "            res += str(i) * C[i]\n",
    "        if res and res[0] == '0':return '0'\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "       cnts = [0] * 10\n",
    "       mod = 0\n",
    "       for d in digits:\n",
    "          cnts[d] += 1\n",
    "          mod += d\n",
    "          mod %= 3\n",
    "       if mod == 1:\n",
    "          f = False\n",
    "          for i in (1, 4, 7):\n",
    "             if cnts[i]:\n",
    "                cnts[i] -= 1\n",
    "                f = True\n",
    "                break\n",
    "          if not f:\n",
    "             c = 2\n",
    "             for i in (2, 5, 8):\n",
    "                while cnts[i] and c:\n",
    "                   cnts[i] -= 1\n",
    "                   c -= 1\n",
    "       if mod == 2:\n",
    "          f = False\n",
    "          for i in (2, 5, 8):\n",
    "             if cnts[i]:\n",
    "                cnts[i] -= 1\n",
    "                f = True\n",
    "                break\n",
    "          if not f:\n",
    "             c = 2\n",
    "             for i in (1, 4, 7):\n",
    "                while cnts[i] and c:\n",
    "                   cnts[i] -= 1\n",
    "                   c -= 1\n",
    "       s = \"\"\n",
    "       for x in range(9, -1, -1):\n",
    "          while cnts[x] > 0:\n",
    "             s += str(x)\n",
    "             cnts[x] -= 1\n",
    "       if len(s) > 0 and s[0] == '0':\n",
    "          return \"0\"\n",
    "       return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt = [0]*10\n",
    "        modulo = [0]*3 # %3,有0，1，2三种情况\n",
    "        s = 0\n",
    "        for digit in digits:\n",
    "            cnt[digit] += 1\n",
    "            modulo[digit%3] += 1\n",
    "            s += digit\n",
    "        remove_mod,res = 0,0\n",
    "        # 需要删除一个\n",
    "        if s%3 == 1:\n",
    "            remove_mod,res = (1,1) if modulo[1] >= 1 else (2,2)\n",
    "        elif s%3 == 2:\n",
    "            remove_mod,res = (2,1) if modulo[2] >= 1 else (1,2)\n",
    "        \n",
    "        ans = ''\n",
    "        for i in range(0,10):\n",
    "            for j in range(cnt[i]):\n",
    "                if res > 0 and remove_mod == i%3:\n",
    "                    res -= 1\n",
    "                else:\n",
    "                    ans += str(i)\n",
    "        if len(ans) > 0 and ans[-1] == '0':\n",
    "            ans = '0'\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        lst=digits\n",
    "        str1=\"\"\n",
    "        s=sum(lst)\n",
    "        k=s%3\n",
    "        if(k!=0):\n",
    "            for i in range(k,10,3):\n",
    "                if(i in lst):\n",
    "                    del lst[lst.index(i)]\n",
    "                    break\n",
    "            if(sum(lst)%3!=0):\n",
    "                if(k==1):\n",
    "                    for i in [[2,2],[2,5],[5,5],[2,8],[5,8],[8,8]]:\n",
    "                        if(i[0] in lst):\n",
    "                            del lst[lst.index(i[0])]\n",
    "                            if(i[1] in lst):\n",
    "                                del lst[lst.index(i[1])]\n",
    "                                break\n",
    "                            else:\n",
    "                                lst.append(i[0])\n",
    "                else:\n",
    "                    for i in [[1,1],[1,4],[4,4],[1,7],[4,7],[7,7]]:\n",
    "                        if(i[0] in lst):\n",
    "                            del lst[lst.index(i[0])]\n",
    "                            if(i[1] in lst):\n",
    "                                del lst[lst.index(i[1])]\n",
    "                                break\n",
    "                            else:\n",
    "                                lst.append(i[0])\n",
    "        if(len(lst)==0):\n",
    "            return \"\"\n",
    "        if(sum(lst)==0):\n",
    "            return \"0\"\n",
    "        lst=sorted(lst,reverse=True)\n",
    "        for num in lst:\n",
    "            str1=str1+str(num)\n",
    "        return str1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        arr = [[] for _ in range(3)]\n",
    "        s = 0\n",
    "        for x in digits:\n",
    "            i = x % 3\n",
    "            arr[i].append(x)\n",
    "            s += i\n",
    "        rest = s % 3\n",
    "        if rest == 1:\n",
    "            if arr[1]:\n",
    "                arr[1].sort(reverse=True)\n",
    "                arr[1].pop()\n",
    "            else:\n",
    "                arr[2].sort(reverse=True)\n",
    "                arr[2].pop()\n",
    "                arr[2].pop()\n",
    "        elif rest == 2:\n",
    "            if arr[2]:\n",
    "                arr[2].sort(reverse=True)\n",
    "                arr[2].pop()\n",
    "            else:\n",
    "                arr[1].sort(reverse=True)\n",
    "                arr[1].pop()\n",
    "                arr[1].pop()\n",
    "        ans = arr[0] + arr[1] + arr[2]\n",
    "        ans.sort(reverse=True)\n",
    "        if not ans:\n",
    "            return ''\n",
    "        if ans[0] == 0:\n",
    "            return '0'\n",
    "        s = ''\n",
    "        for c in ans:\n",
    "            s += str(c)\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        s = 0\n",
    "        modulo = [0]*3\n",
    "        cnt = [0]*10\n",
    "        # 0,1,2\n",
    "        for x in digits:\n",
    "            cnt[x] += 1\n",
    "            modulo[x%3] += 1\n",
    "            s += x\n",
    "        remove,res = 0,0\n",
    "        if s%3 == 1:\n",
    "            remove,res = (1,1) if modulo[1] else (2,2)\n",
    "        if s%3 == 2:\n",
    "            remove,res = (2,1) if modulo[2] else (1,2)\n",
    "        ans = ''\n",
    "        for i in range(0,10):\n",
    "            for j in range(cnt[i]):\n",
    "                if res and i%3 == remove:\n",
    "                    res -= 1\n",
    "                else:\n",
    "                    ans += str(i)\n",
    "        if len(ans) > 0 and ans[-1] == '0':\n",
    "            return '0'\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        s = 0\n",
    "        counter = collections.Counter()\n",
    "        mod_counter = collections.Counter()\n",
    "        for d in digits:\n",
    "            counter[int(d)] += 1 \n",
    "            mod_counter[int(d) % 3] += 1 \n",
    "            s += int(d)\n",
    "        if s % 3 == 0:\n",
    "            rest, m = 0, 0\n",
    "        elif s % 3 == 1:\n",
    "            if mod_counter[1] > 0:\n",
    "                rest, m = 1, 1\n",
    "            else:\n",
    "                rest, m = 2, 2 \n",
    "        else:\n",
    "            if mod_counter[2] > 0:\n",
    "                rest, m = 1, 2 \n",
    "            else:\n",
    "                rest, m = 2, 1\n",
    "        res = ''\n",
    "        for val in range(10):\n",
    "            for _ in range(counter[val]):\n",
    "                if val % 3 == m and rest > 0:\n",
    "                    rest -= 1 \n",
    "                    continue\n",
    "                res += str(val)\n",
    "        if rest > 0:\n",
    "            return ''\n",
    "        if len(res) > 1 and res[-1] == '0':\n",
    "            res = '0'\n",
    "        return res[::-1]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        dic={}\n",
    "        for i in digits:\n",
    "            dic[i%3]=dic.get(i%3,[])+[i]\n",
    "        ld2=len(dic.get(2,[]))\n",
    "        ld1=len(dic.get(1,[]))\n",
    "        if ld1==0 and ld2==0:\n",
    "            use=dic.get(0,[])\n",
    "            heapq.heapify(use)\n",
    "        elif ld1==0:\n",
    "            temp=dic.get(2,[])\n",
    "            heapq.heapify(temp)\n",
    "            i=ld2%3\n",
    "            while i:\n",
    "                heapq.heappop(temp)\n",
    "                i-=1\n",
    "            use=dic.get(0,[])+temp\n",
    "            heapq.heapify(use)\n",
    "        elif ld2==0:\n",
    "            temp=dic.get(1,[])\n",
    "            heapq.heapify(temp)\n",
    "            i=ld1%3\n",
    "            while i:\n",
    "                heapq.heappop(temp)\n",
    "                i-=1\n",
    "            use=dic.get(0,[])+temp\n",
    "            heapq.heapify(use)\n",
    "        elif ld2<=ld1:\n",
    "            use=[]\n",
    "            if (ld1-ld2)%3==0:\n",
    "                #所有数字都参与\n",
    "                use=digits\n",
    "                heapq.heapify(use)\n",
    "            elif (ld1-ld2)%3==1:\n",
    "                temp=dic.get(1,[])\n",
    "                heapq.heapify(temp)\n",
    "                heapq.heappop(temp)\n",
    "                #删除一个最小的数字\n",
    "                use=dic.get(0,[])+dic.get(2,[])+temp\n",
    "                heapq.heapify(use)              \n",
    "            else:\n",
    "                if (ld2*2+(ld1-ld2)//3)<=((ld1//3)*3+min(ld1%3,ld2)*2):\n",
    "                    if ld1%3>0:\n",
    "                        temp1=heapq.nlargest(min(ld1%3,ld2),dic.get(2,[]))\n",
    "                        temp=dic.get(1,[])\n",
    "                        heapq.heapify(temp)\n",
    "                        i=ld1%3-min(ld1%3,ld2)\n",
    "                        while i>0:\n",
    "                            heapq.heappop(temp)\n",
    "                            i-=1\n",
    "                        use=temp+dic.get(0,[])+temp1\n",
    "                    else:\n",
    "                        use=dic.get(0,[])+dic.get(1,[])\n",
    "                    heapq.heapify(use)\n",
    "                else:\n",
    "                    #删除1个最小的数字\n",
    "                    temp=dic.get(2,[])\n",
    "                    heapq.heapify(temp)\n",
    "                    heapq.heappop(temp)\n",
    "                    # heapq.heappop(temp)\n",
    "                    use=dic.get(0,[])+dic.get(1,[])+temp\n",
    "                    heapq.heapify(use)\n",
    "        else:\n",
    "            i=(ld2-ld1)%3\n",
    "            if i==2:\n",
    "                temp=dic.get(1,[])\n",
    "                heapq.heapify(temp)\n",
    "                heapq.heappop(temp)\n",
    "                use=dic.get(0,[])+dic.get(2,[])+temp\n",
    "            else:\n",
    "                #选择前len(dic[1])大的dic[2]\n",
    "                temp=dic.get(2,[])\n",
    "                heapq.heapify(temp)\n",
    "                \n",
    "\n",
    "                while i>0:\n",
    "                    heapq.heappop(temp)\n",
    "                    i-=1\n",
    "                use=dic.get(0,[])+dic.get(1,[])+temp\n",
    "            heapq.heapify(use)\n",
    "        res=''\n",
    "        while use:\n",
    "            nxt=heapq.heappop(use)\n",
    "            res=str(nxt)+res\n",
    "        \n",
    "        while len(res)>1 and res[0]=='0' :\n",
    "            res=res[1:]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        n = len(digits)\n",
    "        #由大到小\n",
    "        #位数上的损失比单个的损失来的大，先找\n",
    "        digits.sort()\n",
    "        # if digits[-1] == 0:\n",
    "            # return \"0\"\n",
    "        d = defaultdict(list)\n",
    "        su = 0\n",
    "        for i, x in enumerate(digits):\n",
    "            if x % 3 == 0:\n",
    "                d[0].append(i)\n",
    "            elif x % 3 == 1:\n",
    "                d[1].append(i)\n",
    "            elif x % 3 == 2:\n",
    "                d[2].append(i)\n",
    "            su = (su + x) % 3\n",
    "        def form(skip: Set[int]) -> str:\n",
    "            ans = \"\"\n",
    "            for i, x in enumerate(digits):\n",
    "                if i not in skip:\n",
    "                    ans = str(x) + ans\n",
    "            return ans \n",
    "        ss =set()\n",
    "        if su % 3 == 0:\n",
    "            if digits[-1] == 0:\n",
    "                return '0'\n",
    "            return form(ss) \n",
    "        elif su % 3 == 1:\n",
    "            if d[1]:\n",
    "                ss.add(d[1][0])\n",
    "                ans = form(ss)\n",
    "                if ans and ans[0] == '0':\n",
    "                    return '0'\n",
    "                return ans\n",
    "            elif len(d[2]) > 1:\n",
    "                ss.add(d[2][0])\n",
    "                ss.add(d[2][1])\n",
    "                ans = form(ss)    \n",
    "                if ans and ans[0] == '0':\n",
    "                    return '0'\n",
    "                return ans\n",
    "            else:\n",
    "                return \"\"\n",
    "        else:\n",
    "            if d[2]:\n",
    "                ss.add(d[2][0])\n",
    "                ans = form(ss)\n",
    "                if ans and ans[0] == '0':\n",
    "                    return '0'\n",
    "                return ans\n",
    "            elif len(d[1]) > 1:\n",
    "                ss.add(d[1][0])\n",
    "                ss.add(d[1][1])\n",
    "                ans = form(ss)\n",
    "                if ans and ans[0] == '0':\n",
    "                    return '0'\n",
    "                return ans\n",
    "            else:\n",
    "                return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        \n",
    "        x = sum(digits) % 3\n",
    "        digits.sort()\n",
    "        if x != 0:\n",
    "            flag = False\n",
    "            for num in digits:\n",
    "                if num % 3 == x:\n",
    "                    digits.remove(num)\n",
    "                    flag = True\n",
    "                    break\n",
    "            if not flag:\n",
    "                lst=[]\n",
    "                for num in digits:\n",
    "                    if num % 3 == (3 - x):\n",
    "                        lst.append(num)\n",
    "                        \n",
    "\n",
    "                        if len(lst) == 2:\n",
    "                            break\n",
    "                \n",
    "                for num in lst:\n",
    "                    digits.remove(num)\n",
    "        digits.reverse()\n",
    "        ans = [str(num)for num in digits]\n",
    "        if  ans and ans[0] == \"0\":\n",
    "            return \"0\"\n",
    "        return \"\".join(ans)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        digits.sort()\n",
    "        sum_i = sum(digits)\n",
    "        index_list = [None, []]\n",
    "        if sum_i % 3 == 0:\n",
    "            pass\n",
    "        else:\n",
    "            if sum_i % 3 == 1:\n",
    "                for i in range(len(digits)):\n",
    "                    if digits[i] % 3 == 1:\n",
    "                        index_list[0] = i\n",
    "                        break\n",
    "                    if digits[i] % 3 == 2 and len(index_list[1]) < 2:\n",
    "                        index_list[1].append(i)\n",
    "            if sum_i % 3 == 2:\n",
    "                for i in range(len(digits)):\n",
    "                    if digits[i] % 3 == 2:\n",
    "                        index_list[0] = i\n",
    "                        break\n",
    "                    if digits[i] % 3 == 1 and len(index_list[1]) < 2:\n",
    "                        index_list[1].append(i)\n",
    "            if index_list[0] != None:\n",
    "                digits.pop(index_list[0])\n",
    "            elif len(index_list[1]) == 2:\n",
    "                digits.pop(index_list[1][1])\n",
    "                digits.pop(index_list[1][0])\n",
    "            else:\n",
    "                return \"\"\n",
    "        digits.reverse()\n",
    "        result = \"\".join([str(i) for i in digits])\n",
    "        if result:\n",
    "            while result and result[0] == \"0\":\n",
    "                result = result[1:]\n",
    "            if not result:\n",
    "                return \"0\"\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        digits.sort()\n",
    "        x = sum(digits) % 3\n",
    "        # 模0则数字全取\n",
    "        if x != 0:\n",
    "            flag = False\n",
    "            for num in digits:\n",
    "                # 有一个数字跟总和模相同，去掉这个最小的数字就可以\n",
    "                if num % 3 == x:\n",
    "                    digits.remove(num)\n",
    "                    flag = True\n",
    "                    break\n",
    "            if not flag:\n",
    "                # 否则需要去掉两个最小的数字\n",
    "                lst = []\n",
    "                for num in digits:\n",
    "                    if num % 3 == (3 - x):\n",
    "                        lst.append(num)\n",
    "                        if len(lst) >= 2:\n",
    "                            break\n",
    "                for num in lst:\n",
    "                    digits.remove(num)\n",
    "        digits.reverse()\n",
    "        ans = [str(d) for d in digits]\n",
    "        # 全为0则只能为0\n",
    "        if ans and ans[0] == \"0\":\n",
    "            return \"0\"\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        digits.sort()\n",
    "        x = sum(digits) % 3\n",
    "        if x:\n",
    "            found_x = False     \n",
    "            for i in digits:\n",
    "                if i % 3 == x:\n",
    "                    digits.remove(i)\n",
    "                    found_x = True\n",
    "                    break \n",
    "            if not found_x:\n",
    "                temp = []\n",
    "                for i in digits:\n",
    "                    if i % 3 == 3 - x:\n",
    "                        temp.append(i)\n",
    "                        if len(temp) >= 2:\n",
    "                            break\n",
    "                for i in temp:\n",
    "                    digits.remove(i)\n",
    "        if digits and digits[-1] == 0:\n",
    "            return '0'\n",
    "        digits = list(map(str, digits))\n",
    "        return ''.join(digits[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt = [0] * 10\n",
    "        m = [0] * 3\n",
    "        s = 0\n",
    "        for d in digits:\n",
    "            cnt[d] += 1\n",
    "            m[d % 3] += 1\n",
    "            s += d\n",
    "        \n",
    "        re_mod, re_cnt = 0, 0\n",
    "        if s % 3 == 1:\n",
    "            if m[1] > 0:\n",
    "                re_mod = 1\n",
    "                re_cnt = 1\n",
    "            else:\n",
    "                re_mod = 2\n",
    "                re_cnt = 2\n",
    "        elif s % 3 == 2:\n",
    "            if m[2] > 0:\n",
    "                re_mod = 2\n",
    "                re_cnt = 1\n",
    "            else:\n",
    "                re_mod = 1\n",
    "                re_cnt = 2\n",
    "        \n",
    "        tmp = []\n",
    "        for i in range(10):\n",
    "            for j in range(cnt[i]):\n",
    "                if re_cnt > 0 and i % 3 == re_mod:\n",
    "                    re_cnt -= 1\n",
    "                else:\n",
    "                    tmp.append(str(i))\n",
    "        \n",
    "        if len(tmp) > 0 and tmp[-1] == '0':\n",
    "            return '0'\n",
    "        return ''.join(tmp[::-1])\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\r\n",
    "        digits.sort()\r\n",
    "        x = sum(digits) % 3\r\n",
    "        if x != 0:\r\n",
    "            flag = False\r\n",
    "            # 删除一个最小的摸与x相等的元素\r\n",
    "            for num in digits:\r\n",
    "                if num % 3 == x:\r\n",
    "                    digits.remove(num)\r\n",
    "                    flag = True\r\n",
    "                    break\r\n",
    "            if not flag:\r\n",
    "                lst = []\r\n",
    "                # 删除两个最小的模为（3-x）的元素\r\n",
    "                for num in digits:\r\n",
    "                    if num % 3 == (3 - x):\r\n",
    "                        lst.append(num)\r\n",
    "                        if len(lst) >= 2:\r\n",
    "                            break\r\n",
    "                for num in lst:\r\n",
    "                    digits.remove(num)\r\n",
    "        digits.reverse()\r\n",
    "        ans = [str(x) for x in digits]\r\n",
    "        if ans and ans[0] == '0':\r\n",
    "            return '0'\r\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt = [0] * 10\n",
    "        mod = [0] * 3\n",
    "        s = 0\n",
    "        \n",
    "        for d in digits:\n",
    "            cnt[d] += 1\n",
    "            mod[d % 3] += 1\n",
    "            s += d\n",
    "        \n",
    "        del_mod, rest = 0, 0\n",
    "        if s % 3 == 1:\n",
    "            del_mod, rest = (1, 1) if mod[1] >= 1 else (2, 2)\n",
    "        elif s % 3 == 2:\n",
    "            del_mod, rest = (2, 1) if mod[2] >= 1 else (1, 2)\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(10):\n",
    "            for j in range(cnt[i]):\n",
    "                if i % 3 == del_mod and rest > 0:\n",
    "                    rest -= 1\n",
    "                    continue\n",
    "                else:\n",
    "                    ans.append(str(i))\n",
    "        \n",
    "        if ans and ans[-1] == '0':\n",
    "            return '0'\n",
    "        else:\n",
    "            return \"\".join(ans[::-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        digits.sort()\n",
    "        sum_i = sum(digits)\n",
    "        index_list = [None, []]\n",
    "        if sum_i % 3 == 0:\n",
    "            pass\n",
    "        else:\n",
    "            if sum_i % 3 == 1:\n",
    "                for i in range(len(digits)):\n",
    "                    if digits[i] % 3 == 1:\n",
    "                        index_list[0] = i\n",
    "                        break\n",
    "                    if digits[i] % 3 == 2 and len(index_list[1]) < 2:\n",
    "                        index_list[1].append(i)\n",
    "            if sum_i % 3 == 2:\n",
    "                for i in range(len(digits)):\n",
    "                    if digits[i] % 3 == 2:\n",
    "                        index_list[0] = i\n",
    "                        break\n",
    "                    if digits[i] % 3 == 1 and len(index_list[1]) < 2:\n",
    "                        index_list[1].append(i)\n",
    "            if index_list[0] != None:\n",
    "                digits.pop(index_list[0])\n",
    "            elif len(index_list[1]) == 2:\n",
    "                digits.pop(index_list[1][1])\n",
    "                digits.pop(index_list[1][0])\n",
    "            else:\n",
    "                return \"\"\n",
    "        result = \"\".join([str(digits[i]) for i in range(len(digits)-1, -1, -1)])\n",
    "        if result:\n",
    "            while result and result[0] == \"0\":\n",
    "                result = result[1:]\n",
    "            if not result:\n",
    "                return \"0\"\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        digits.sort(reverse=True)\n",
    "        a = 0\n",
    "        for i in range(len(digits)):\n",
    "            a = a + digits[i]\n",
    "            digits[i]=str(digits[i])\n",
    "        n=''.join(digits)\n",
    "        judge = a%3\n",
    "        if a==0:\n",
    "            return '0'\n",
    "        elif judge==0:\n",
    "            return n\n",
    "        elif judge==1:\n",
    "            if digits.count('1')>0:\n",
    "                digits.remove('1')\n",
    "            elif digits.count('4')>0:\n",
    "                digits.remove('4')\n",
    "            elif digits.count('7')>0:\n",
    "                digits.remove('7')\n",
    "            elif digits.count('2')>1:\n",
    "                digits.remove('2')\n",
    "                digits.remove('2')\n",
    "            elif digits.count('2')>0 and digits.count('5')>0:\n",
    "                digits.remove('2')\n",
    "                digits.remove('5')\n",
    "            elif digits.count('5')>1:\n",
    "                digits.remove('5')\n",
    "                digits.remove('5')\n",
    "            elif digits.count('2')>0 and digits.count('8')>0:\n",
    "                digits.remove('2')\n",
    "                digits.remove('8')\n",
    "            elif digits.count('5')>0 and digits.count('8')>0:\n",
    "                digits.remove('5')\n",
    "                digits.remove('8')\n",
    "            elif digits.count('8')>1:\n",
    "                digits.remove('8')\n",
    "                digits.remove('8')\n",
    "            if digits.count('0')==len(digits) and len(digits)!=0:\n",
    "                return '0'\n",
    "            else:\n",
    "                return ''.join(digits)\n",
    "        elif judge==2:\n",
    "            if digits.count('2')>0:\n",
    "                digits.remove('2')\n",
    "            elif digits.count('5')>0:\n",
    "                digits.remove('5')\n",
    "            elif digits.count('8')>0:\n",
    "                digits.remove('8')\n",
    "            elif digits.count('1')>1:\n",
    "                digits.remove('1')\n",
    "                digits.remove('1')\n",
    "            elif digits.count('1')>0 and digits.count('4')>0:\n",
    "                digits.remove('1')\n",
    "                digits.remove('4')\n",
    "            elif digits.count('4')>1:\n",
    "                digits.remove('4')\n",
    "                digits.remove('4')\n",
    "            elif digits.count('1')>0 and digits.count('7')>0:\n",
    "                digits.remove('1')\n",
    "                digits.remove('7')\n",
    "            elif digits.count('4')>0 and digits.count('7')>0:\n",
    "                digits.remove('4')\n",
    "                digits.remove('7')\n",
    "            elif digits.count('7')>1:\n",
    "                digits.remove('7')\n",
    "                digits.remove('7')\n",
    "            if digits.count('0')==len(digits) and len(digits)!=0:\n",
    "                return '0'\n",
    "            else:\n",
    "                return ''.join(digits)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        \"\"\"\n",
    "        记数组之和为s\n",
    "        if s%3==0 那么选择所有元素，且顺序从大到小选择即可\n",
    "        elif s%3==1 从数组中删除一个模3为1的数，如果没有则删除两个模3为2的数，一定是存在这两种的 不然不可能总和余数为1\n",
    "        else 从数组中删除一个模3为2的数,如果没有就删除两个模3为1的数\n",
    "        具体操作：\n",
    "        用cnt和times分别记录1-9出现次数，和余数0~2出现的次数，同时求出和s\n",
    "        根据s%3和times的情况 确定要删除模为几 同时删除的次数\n",
    "        \"\"\"\n",
    "        cnt,times = [0 for _ in range(10)],[0 for _ in range(3)]\n",
    "        s = 0\n",
    "        for d in digits:\n",
    "            cnt[d] += 1\n",
    "            times[d%3] += 1\n",
    "            s += d\n",
    "        del_mod,del_cnt = 0,0 #删除的模以及次数 初始化为0\n",
    "        if s%3 == 1:\n",
    "            del_mod,del_cnt = (1,1) if times[1]>=1 else (2,2) \n",
    "        elif s%3 == 2:\n",
    "            del_mod,del_cnt = (2,1) if times[2]>=1 else (1,2) \n",
    "        rs = []\n",
    "        for i in range(10):\n",
    "            for j in range(cnt[i]):\n",
    "                if del_cnt>0 and i%3 == del_mod:\n",
    "                    del_cnt -= 1\n",
    "                else:\n",
    "                    rs.append(str(i))\n",
    "        return \"0\" if len(rs)>0 and rs[-1]=='0' else \"\".join(rs[::-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        digits.sort()\n",
    "        s = sum(digits)\n",
    "        if s == 0:\n",
    "            return \"0\"\n",
    "        de = set()\n",
    "        if s % 3 == 1:\n",
    "            for i, d in enumerate(digits):\n",
    "                if d % 3 == 1:\n",
    "                    de.add(i)\n",
    "                    break\n",
    "            if len(de) == 0:\n",
    "                for i, d in enumerate(digits):\n",
    "                    if d % 3 == 2:\n",
    "                        de.add(i)\n",
    "                        if len(de) == 2:\n",
    "                            break\n",
    "        elif s % 3 == 2:\n",
    "            for i, d in enumerate(digits):\n",
    "                if d % 3 == 2:\n",
    "                    de.add(i)\n",
    "                    break\n",
    "            if len(de) == 0:\n",
    "                for i, d in enumerate(digits):\n",
    "                    if d % 3 == 1:\n",
    "                        de.add(i)\n",
    "                        if len(de) == 2:\n",
    "                            break\n",
    "        ne = []\n",
    "        f = False\n",
    "        ns = 0\n",
    "        for i, d in enumerate(digits):\n",
    "            if d == 0:\n",
    "                f = True\n",
    "            if i not in de:\n",
    "                ne.append(str(d))\n",
    "                ns += d\n",
    "        if ns % 3 == 0 and ns != 0:\n",
    "            ne.sort()\n",
    "            ne.reverse()\n",
    "            return \"\".join(ne)\n",
    "        else:\n",
    "            if f:\n",
    "                return \"0\"\n",
    "            else:\n",
    "                return \"\"\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        if digits.count(0) == len(digits):\n",
    "            return '0'\n",
    "        digits.sort()\n",
    "        cnt = sum(digits)\n",
    "        digits2 = [x%3 for x in digits]\n",
    "        cnt2 = sum(digits2)\n",
    "        if cnt2 % 3==0:\n",
    "            digits.reverse()\n",
    "            return ''.join(map(str,digits)) if digits.count(0) != len(digits) else '0'\n",
    "        else :\n",
    "            x = cnt2 % 3\n",
    "            for i in range(len(digits2)):\n",
    "                if digits2[i] == x:\n",
    "                    lst = digits[:i]+digits[i+1:]\n",
    "                    lst.reverse()\n",
    "                    if not lst:\n",
    "                        return ''\n",
    "                    if lst.count(0) == len(lst):\n",
    "                        return '0'\n",
    "                    return ''.join(map(str,lst))\n",
    "            selected =[]\n",
    "            for i in range(len(digits2)):\n",
    "                if digits2[i]==3-x:\n",
    "                    selected.append(i)\n",
    "                if len(selected)==2:\n",
    "                    lst = digits[:selected[0]]+digits[selected[0]+1:selected[1]]+digits[selected[1]+1:]\n",
    "                    lst.reverse()\n",
    "                    if not lst:\n",
    "                        return ''\n",
    "                    if lst.count(0) == len(lst):\n",
    "                        return '0'               \n",
    "                    return ''.join(map(str,lst))\n",
    "                      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        remains = defaultdict(list)\n",
    "        for digit in digits:\n",
    "            if digit % 3 == 0:\n",
    "                remains[0].append(digit)\n",
    "            elif digit % 3 == 1:\n",
    "                remains[1].append(digit)\n",
    "            else:\n",
    "                remains[2].append(digit)\n",
    "        remains[1].sort(reverse=True)\n",
    "        remains[2].sort(reverse=True)\n",
    "        a = remains[1]\n",
    "        b = remains[2]\n",
    "        if len(b) % 3 > len(a) % 3:\n",
    "            a, b = b, a\n",
    "        if len(a) % 3 == 1:\n",
    "            if len(b) % 3 == 0:\n",
    "                a.pop()\n",
    "        elif len(a) % 3 == 2:\n",
    "            if len(b) % 3 == 1:\n",
    "                a.pop()\n",
    "            elif len(b) % 3 == 0:\n",
    "                if len(b) >= 3:\n",
    "                    b.pop()\n",
    "                else:\n",
    "                    a.pop()\n",
    "                    a.pop()\n",
    "        result = remains[0] + remains[1] + remains[2]\n",
    "        result.sort(reverse=True)\n",
    "        if len(result) > 0 and result[0] == 0:\n",
    "            return \"0\"\n",
    "        return ''.join([str(num) for num in result])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        digits.sort()\n",
    "        sum_i = sum(digits)\n",
    "        mod_list = [i % 3 for i in digits]\n",
    "        if sum_i % 3 == 1:\n",
    "            if mod_list.count(1) >= 1:\n",
    "                digits.pop(mod_list.index(1))\n",
    "            elif mod_list.count(2) >= 2:\n",
    "                index1 = mod_list.index(2)\n",
    "                index2 = mod_list.index(2, index1+1)\n",
    "                digits.pop(index2)\n",
    "                digits.pop(index1)\n",
    "            else:\n",
    "                digits = []\n",
    "        elif sum_i % 3 == 2:\n",
    "            if mod_list.count(2) >= 1:\n",
    "                digits.pop(mod_list.index(2))\n",
    "            elif mod_list.count(1) >= 2:\n",
    "                index1 = mod_list.index(1)\n",
    "                index2 = mod_list.index(1, index1+1)\n",
    "                digits.pop(index2)\n",
    "                digits.pop(index1)\n",
    "            else:\n",
    "                digits = []\n",
    "        digits.reverse()\n",
    "        result = \"\".join([str(i) for i in digits])\n",
    "        if result:\n",
    "            while result and result[0] == \"0\":\n",
    "                result = result[1:]\n",
    "            if not result:\n",
    "                result = \"0\"\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        a = b = c = 0\n",
    "        arr1 = []\n",
    "        arr2 = []\n",
    "        arr3 = []\n",
    "        for d in digits:\n",
    "            if d % 3 == 0:\n",
    "                arr1.append(d)\n",
    "                a += 1\n",
    "            elif d % 3 == 1:\n",
    "                arr2.append(d)\n",
    "                b += 1\n",
    "            else:\n",
    "                arr3.append(d)\n",
    "                c += 1\n",
    "        if a == 0 and (b == 0 or c == 0) and (b + c < 3):\n",
    "            return ''\n",
    "        ans = arr1\n",
    "        arr2.sort(reverse=True)\n",
    "        arr3.sort(reverse=True)\n",
    "        p, q = b % 3, c % 3\n",
    "        if p == q:\n",
    "            ans = ans + arr2 + arr3\n",
    "        if p == 0 and q == 2:\n",
    "            if b == 0:\n",
    "                ans = ans + arr3[:-2]\n",
    "            else:\n",
    "                ans = ans + arr2[:-1] + arr3\n",
    "        if (p == 1 and q == 0) or (p == 2 and q == 1):\n",
    "            ans = ans + arr2[:-1] + arr3\n",
    "        if (p == 0 and q == 1) or (p == 1 and q == 2):\n",
    "            ans = ans + arr2 + arr3[:-1]\n",
    "        if p == 2 and q == 0:\n",
    "            if c == 0:\n",
    "                ans = ans + arr2[:-2]\n",
    "            else:\n",
    "                ans = ans + arr2 + arr3[:-1]\n",
    "        ans.sort(reverse=True)\n",
    "        if ans[0] == 0:\n",
    "            return '0'\n",
    "        else:\n",
    "            ans = [str(x) for x in ans]\n",
    "            return ''.join(ans)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        test = [[] for i in range(3)]\n",
    "        for i in digits:\n",
    "            test[i % 3].append(i)\n",
    "        test[1].sort(reverse=True)\n",
    "        test[2].sort(reverse=True)\n",
    "        if sum(digits) % 3 == 1:\n",
    "            if test[1]:\n",
    "                test[1].pop()\n",
    "            else:\n",
    "                test[2].pop()\n",
    "                test[2].pop()\n",
    "        elif sum(digits) % 3 == 2:\n",
    "            if test[2]:\n",
    "                test[2].pop()\n",
    "            else:\n",
    "                test[1].pop()\n",
    "                test[1].pop()\n",
    "        res = []\n",
    "        for i in test:\n",
    "            res += i\n",
    "        res.sort(reverse=True)\n",
    "        if res and res[0] == 0:\n",
    "            return \"0\"\n",
    "        return \"\".join(map(str, res))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        digits.sort(reverse=True)\n",
    "        if digits[0]=='0':return '0'\n",
    "        cnt=defaultdict(list)\n",
    "        mod=0\n",
    "    \n",
    "        for v in digits:\n",
    "            v=int(v)\n",
    "            mod+=v\n",
    "            cnt[v%3].append(str(v))\n",
    "        \n",
    "        mod%=3\n",
    "\n",
    "        print(mod,cnt)\n",
    "        if mod==1:\n",
    "            if cnt[1]:\n",
    "                cnt[1].pop()\n",
    "            elif len(cnt[2])>=2:\n",
    "                cnt[2].pop()\n",
    "                cnt[2].pop()\n",
    "            else:\n",
    "                return \"\"\n",
    "        elif mod==2:\n",
    "            if cnt[2]:\n",
    "                cnt[2].pop()\n",
    "            elif len(cnt[1])>=2:\n",
    "                cnt[1].pop()\n",
    "                cnt[1].pop()\n",
    "            else:\n",
    "                return \"\"\n",
    "        s=[]\n",
    "        print(cnt)\n",
    "        for k,v in cnt.items():\n",
    "            if v:\n",
    "                s.extend(v)\n",
    "        \n",
    "        if not s:return \"\"\n",
    "        s.sort(reverse=True)\n",
    "        print(s)\n",
    "\n",
    "        res=\"\".join(s).lstrip(\"0\")\n",
    "        return res if res else \"0\"\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        cnt = [[], [], []]\n",
    "        for d in digits:\n",
    "            cnt[d % 3].append(d)\n",
    "        cnt[1].sort(reverse=True)\n",
    "        cnt[2].sort(reverse=True)\n",
    "\n",
    "        ans = cnt[0][::]  # mod 0都可以选\n",
    "        \n",
    "        m = sum(digits) % 3\n",
    "        if m == 0:\n",
    "            ans = sorted(digits)\n",
    "        elif m == 1:  # 从cnt[1]中删除1个或者从cnt[2]里面删除2个\n",
    "            if cnt[1]:\n",
    "                cnt[1].pop()\n",
    "            else:\n",
    "                cnt[2].pop()\n",
    "                cnt[2].pop()\n",
    "            ans.extend(cnt[1])\n",
    "            ans.extend(cnt[2])\n",
    "        elif m == 2:\n",
    "            if cnt[2]:\n",
    "                cnt[2].pop()\n",
    "            else:\n",
    "                cnt[1].pop()\n",
    "                cnt[1].pop()\n",
    "            ans.extend(cnt[1])\n",
    "            ans.extend(cnt[2])\n",
    "\n",
    "        \n",
    "        \n",
    "        ans.sort(reverse=True)\n",
    "        # 去掉前导0\n",
    "        i = 0\n",
    "        while i < len(ans) - 1:\n",
    "            if ans[i]:\n",
    "                break\n",
    "            i += 1\n",
    "        return \"\" if not ans else \"\".join(map(str, ans[i:]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        # 总体思路是，凑出所有和能被3整除的数字，然后从大到小拼接起来\n",
    "        # 把所有数字根据除3之后的余数，012分成3组，然后去掉较小的数，使总和能被3整除\n",
    "        S = sum(digits)\n",
    "        if S%3==0:\n",
    "            digits.sort(reverse=True)\n",
    "            res = ''.join([str(e) for e in digits])\n",
    "            if res[0]=='0':\n",
    "                res = \"0\"\n",
    "            return res\n",
    "        \n",
    "        num1,num2,num0 = [],[],[]\n",
    "        for d in digits:\n",
    "            if d%3==0: num0.append(d)\n",
    "            elif d%3==1: num1.append(d)\n",
    "            else: num2.append(d)\n",
    "        num1.sort()\n",
    "        num2.sort()\n",
    "        \n",
    "        if S%3==1:\n",
    "            if len(num1)>0:\n",
    "                num1.pop(0)\n",
    "            else:\n",
    "                num2.pop(0)\n",
    "                num2.pop(0)\n",
    "        else:\n",
    "            if len(num2)>0:\n",
    "                num2.pop(0)\n",
    "            else:\n",
    "                num1.pop(0)\n",
    "                num1.pop(0)\n",
    "        num0.extend(num1)\n",
    "        num0.extend(num2)\n",
    "        if len(num0)==0: return \"\"\n",
    "        num0.sort(reverse=True)\n",
    "        res = ''.join([str(e) for e in num0])\n",
    "        if res[0]=='0':\n",
    "            return \"0\"\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        digits = sorted(digits, reverse = True)\n",
    "        ans = sum(digits)\n",
    "        a0 = [x for x in digits if x%3==0]\n",
    "        a1 = [x for x in digits if x%3==1]\n",
    "        a2 = [x for x in digits if x%3==2]\n",
    "        a1 = sorted(a1)\n",
    "        a2 = sorted(a2)\n",
    "        anslst= []\n",
    "        if ans%3 == 1:\n",
    "            if len(a1) > 0:\n",
    "                del a1[0]\n",
    "            elif len(a2) > 1:\n",
    "                del a2[0]\n",
    "                del a2[0]\n",
    "            else:\n",
    "                return \"\"\n",
    "        if ans%3 == 2:\n",
    "            if len(a2) > 0:\n",
    "                del a2[0]\n",
    "            elif len(a1) > 1:\n",
    "                del a1[0]\n",
    "                del a1[0]\n",
    "            else:\n",
    "                return \"\"\n",
    "        anslst.extend(a0)\n",
    "        anslst.extend(a1)\n",
    "        anslst.extend(a2)\n",
    "        anslst = sorted(anslst, reverse = True)\n",
    "        while len(anslst) > 1 and anslst[0] == 0:\n",
    "            del anslst[0]\n",
    "        return \"\".join([str(x) for x in anslst])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\r\n",
    "        dict = Counter()\r\n",
    "        mod0_dict = []\r\n",
    "        mod1_dict = []\r\n",
    "        mod2_dict = []\r\n",
    "        for item in digits:\r\n",
    "            dict[item] += 1\r\n",
    "            if item%3 == 0:\r\n",
    "                mod0_dict.append(item)\r\n",
    "            elif item%3 == 1:\r\n",
    "                mod1_dict.append(item)\r\n",
    "            else:\r\n",
    "                mod2_dict.append(item)\r\n",
    "                \r\n",
    "        mod0_dict.sort()\r\n",
    "        mod1_dict.sort()\r\n",
    "        mod2_dict.sort()\r\n",
    "        \r\n",
    "        \r\n",
    "        n0 =  len(mod0_dict)\r\n",
    "        n1 =  len(mod1_dict)\r\n",
    "        n2 =  len(mod2_dict)\r\n",
    "        # no valid\r\n",
    "        if n0 == 0 and ( \\\r\n",
    "            (n1 <= 2 and n2 == 0 ) or \\\r\n",
    "            (n2 <= 2 and n1 == 0 )):\r\n",
    "            return \"\"\r\n",
    "        # all zero\r\n",
    "        if dict[0] == n0  and ( \\\r\n",
    "            (n1 <= 2 and n2 == 0 ) or \\\r\n",
    "            (n2 <= 2 and n1 == 0 )):\r\n",
    "            return \"0\"\r\n",
    "        \r\n",
    "        results = mod0_dict\r\n",
    "        \r\n",
    "        while len(mod2_dict) != 0 and len(mod1_dict) != 0:\r\n",
    "            if len(mod2_dict) >= 3 and len(mod1_dict) == 1:\r\n",
    "                results.append(mod2_dict.pop())\r\n",
    "                results.append(mod2_dict.pop())\r\n",
    "                results.append(mod2_dict.pop())\r\n",
    "                continue\r\n",
    "            if len(mod1_dict) >= 3 and len(mod2_dict) == 1:\r\n",
    "                results.append(mod1_dict.pop())\r\n",
    "                results.append(mod1_dict.pop())\r\n",
    "                results.append(mod1_dict.pop())\r\n",
    "                continue\r\n",
    "            results.append(mod1_dict.pop())\r\n",
    "            results.append(mod2_dict.pop())\r\n",
    "        \r\n",
    "        while len(mod2_dict) >= 3:\r\n",
    "            results.append(mod2_dict.pop())\r\n",
    "            results.append(mod2_dict.pop())\r\n",
    "            results.append(mod2_dict.pop())\r\n",
    "        if  len(mod1_dict) >= 3:\r\n",
    "            results.append(mod1_dict.pop())\r\n",
    "            results.append(mod1_dict.pop())\r\n",
    "            results.append(mod1_dict.pop())\r\n",
    "        \r\n",
    "        results.sort(reverse=True)\r\n",
    "        return \"\".join(map(str,results))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        digits.sort(reverse=True)\n",
    "        temp1 = []\n",
    "        temp2 = []\n",
    "        temp3 = []\n",
    "        for digit in digits:\n",
    "            if digit % 3 == 1:\n",
    "                temp1.append(str(digit))\n",
    "            elif digit % 3 == 2:\n",
    "                temp2.append(str(digit))\n",
    "            else:\n",
    "                temp3.append(str(digit))\n",
    "        temp1.sort(reverse=True)\n",
    "        temp2.sort(reverse=True)\n",
    "        l1 = len(temp1)\n",
    "        l2 = len(temp2)\n",
    "        t1 = l1 % 3\n",
    "        t2 = l2 % 3\n",
    "        if t1 == t2:\n",
    "            pass\n",
    "        elif t1 == 1 and t2 == 0:\n",
    "            temp1 = temp1[:-1]\n",
    "        elif t1 == 0 and t2 == 1:\n",
    "            temp2 = temp2[:-1]\n",
    "        elif t1 == 2 and t2 == 0 and l2 != 0:\n",
    "            temp2 = temp2[:-1]\n",
    "        elif t1 == 0 and t2 == 2 and l1 != 0:\n",
    "            temp1 = temp1[:-1]\n",
    "        elif t1 == 2 and t2 == 1:\n",
    "            temp1 = temp1[:-1]\n",
    "        elif t1 == 1 and t2 == 2:\n",
    "            temp2 = temp2[:-1]\n",
    "        else:\n",
    "            temp1 = temp1[:l1 - t1]\n",
    "            temp2 = temp2[:l2 - t2]\n",
    "        ans = ''\n",
    "        x, y, z = 0, 0, 0\n",
    "        while x < len(temp1) or y < len(temp2) or z < len(temp3):\n",
    "            if x == len(temp1) and y == len(temp2):\n",
    "                ans = ans + ''.join(temp3[z:])\n",
    "                break\n",
    "            elif x == len(temp1) and z == len(temp3):\n",
    "                ans = ans + ''.join(temp2[y:])\n",
    "                break\n",
    "            elif y == len(temp2) and z == len(temp3):\n",
    "                ans = ans + ''.join(temp1[x:])\n",
    "                break\n",
    "            elif x == len(temp1):\n",
    "                if int(temp2[y]) >= int(temp3[z]):\n",
    "                    ans = ans + temp2[y]\n",
    "                    y += 1\n",
    "                else:\n",
    "                    ans = ans + temp3[z]\n",
    "                    z += 1\n",
    "            elif y == len(temp2):\n",
    "                if int(temp1[x]) >= int(temp3[z]):\n",
    "                    ans = ans + temp1[x]\n",
    "                    x += 1\n",
    "                else:\n",
    "                    ans = ans + temp3[z]\n",
    "                    z += 1\n",
    "            elif z == len(temp3):\n",
    "                if int(temp1[x]) >= int(temp2[y]):\n",
    "                    ans = ans + temp1[x]\n",
    "                    x += 1\n",
    "                else:\n",
    "                    ans = ans + temp2[y]\n",
    "                    y += 1\n",
    "            else:\n",
    "                if int(temp1[x]) >= int(temp3[z]) and int(temp1[x]) >= int(temp2[y]):\n",
    "                    ans = ans + temp1[x]\n",
    "                    x += 1\n",
    "                elif int(temp2[y]) >= int(temp3[z]) and int(temp2[y]) >= int(temp1[x]):\n",
    "                    ans = ans + temp2[y]\n",
    "                    y += 1\n",
    "                else:\n",
    "                    ans = ans + temp3[z]\n",
    "                    z += 1\n",
    "        if ans == '':\n",
    "            return ''\n",
    "        ans = ans.lstrip('0')\n",
    "        if ans == '':\n",
    "            return '0'\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        candidate = []\n",
    "        hashmap = dict()\n",
    "        hashmap[1], hashmap[2] = [], []\n",
    "        \n",
    "        for i in digits:\n",
    "            if i%3==1:\n",
    "                hashmap[1].append(i)\n",
    "            elif i%3==2:\n",
    "                hashmap[2].append(i)\n",
    "            else:\n",
    "                candidate.append(i)\n",
    "        \n",
    "        hashmap[1].sort(reverse=True)\n",
    "        hashmap[2].sort(reverse=True)\n",
    "\n",
    "        l1, l2 = len(hashmap[1]), len(hashmap[2])\n",
    "\n",
    "        if abs(l2%3-l1%3)==0:\n",
    "            candidate.extend(hashmap[1]+hashmap[2])\n",
    "\n",
    "        elif abs(l2%3-l1%3)==1:\n",
    "            if l2%3>l1%3:\n",
    "                candidate.extend(hashmap[1][:l1])\n",
    "                candidate.extend(hashmap[2][:l2-1])\n",
    "            else:\n",
    "                candidate.extend(hashmap[1][:l1-1])\n",
    "                candidate.extend(hashmap[2][:l2])\n",
    "\n",
    "        else: # 2\n",
    "            if l1%3:\n",
    "                if l2:\n",
    "                    candidate.extend(hashmap[1][:l1])\n",
    "                    candidate.extend(hashmap[2][:l2-1])\n",
    "                else:\n",
    "                    candidate.extend(hashmap[1][:l1//3*3])\n",
    "            elif l2%3:\n",
    "                if l1:\n",
    "                    candidate.extend(hashmap[1][:l1-1])\n",
    "                    candidate.extend(hashmap[2][:l2])\n",
    "                else:\n",
    "                    candidate.extend(hashmap[2][:l2//3*3])    \n",
    "        candidate.sort(reverse=True)\n",
    "        \n",
    "        if candidate and not candidate[0]:\n",
    "            return '0'\n",
    "        candidate = map(str, candidate)\n",
    "        return ''.join(candidate)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        S = sum(digits)\n",
    "        if S%3==0:\n",
    "            digits.sort(reverse=True)\n",
    "            res = ''.join([str(e) for e in digits])\n",
    "            if res[0]=='0':\n",
    "                res = \"0\"\n",
    "            return res\n",
    "        \n",
    "        num1,num2,num0 = [],[],[]\n",
    "        for d in digits:\n",
    "            if d%3==0: num0.append(d)\n",
    "            elif d%3==1: num1.append(d)\n",
    "            else: num2.append(d)\n",
    "        num1.sort()\n",
    "        num2.sort()\n",
    "        \n",
    "        if S%3==1:\n",
    "            if len(num1)>0:\n",
    "                num1.pop(0)\n",
    "            else:\n",
    "                num2.pop(0)\n",
    "                num2.pop(0)\n",
    "        else:\n",
    "            if len(num2)>0:\n",
    "                num2.pop(0)\n",
    "            else:\n",
    "                num1.pop(0)\n",
    "                num1.pop(0)\n",
    "        num0.extend(num1)\n",
    "        num0.extend(num2)\n",
    "        if len(num0)==0: return \"\"\n",
    "        num0.sort(reverse=True)\n",
    "        res = ''.join([str(e) for e in num0])\n",
    "        if res[0]=='0':\n",
    "            return \"0\"\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\n",
    "        \n",
    "        dct = [[] for _ in range(3)]\n",
    "        for num in digits:\n",
    "            dct[num%3].append(num)\n",
    "        s= sum(digits) % 3\n",
    "        if s == 0:\n",
    "            digits.sort(reverse=True)\n",
    "            digits = deque(digits)\n",
    "            while len(digits) >= 2 and digits[0] == 0:\n",
    "                digits.popleft()\n",
    "            return \"\".join(str(x) for x in digits)\n",
    "        if s == 1:\n",
    "            if len(dct[1]) >= 1:\n",
    "                dct[1].sort(reverse=True)\n",
    "                dct[1].pop()\n",
    "                digits = dct[0]+dct[1]+dct[2]\n",
    "                digits.sort(reverse=True)\n",
    "                digits = deque(digits)\n",
    "                while len(digits) >= 2 and digits[0] == 0:\n",
    "                    digits.popleft()\n",
    "                return \"\".join(str(x) for x in digits)\n",
    "            elif len(dct[2]) >= 2:\n",
    "                dct[2].sort(reverse=True)\n",
    "                dct[2].pop()\n",
    "                dct[2].pop()\n",
    "                digits = dct[0] + dct[1] + dct[2]\n",
    "                digits.sort(reverse=True)\n",
    "                digits = deque(digits)\n",
    "                while len(digits) >= 2 and digits[0] == 0:\n",
    "                    digits.popleft()\n",
    "                return \"\".join(str(x) for x in digits)\n",
    "            else:\n",
    "                return \"\"\n",
    "\n",
    "        if len(dct[2]) >= 1:\n",
    "            dct[2].sort(reverse=True)\n",
    "            dct[2].pop()\n",
    "            digits = dct[0] + dct[1] + dct[2]\n",
    "            digits.sort(reverse=True)\n",
    "            digits = deque(digits)\n",
    "            while len(digits) >= 2 and digits[0] == 0:\n",
    "                digits.popleft()\n",
    "            return \"\".join(str(x) for x in digits)\n",
    "        elif len(dct[1]) >= 2:\n",
    "            dct[1].sort(reverse=True)\n",
    "            dct[1].pop()\n",
    "            dct[1].pop()\n",
    "            digits = dct[0] + dct[1] + dct[2]\n",
    "            digits.sort(reverse=True)\n",
    "            digits = deque(digits)\n",
    "            while len(digits) >= 2 and digits[0] == 0:\n",
    "                digits.popleft()\n",
    "            return \"\".join(str(x) for x in digits)\n",
    "        else:\n",
    "            return \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def largestMultipleOfThree(self, digits: List[int]) -> str:\r\n",
    "        # 贪心， 最多只有两个数不会被选\r\n",
    "\r\n",
    "        # 按照 mod 3 进行分类 \r\n",
    "        m0 = []\r\n",
    "        m1 = []\r\n",
    "        m2 = []\r\n",
    "        for x in digits :\r\n",
    "            if x % 3 == 0:\r\n",
    "                m0.append(x)\r\n",
    "            elif x % 3 == 1:\r\n",
    "                m1.append(x)\r\n",
    "            else:\r\n",
    "                m2.append(x)\r\n",
    "        m0.sort(reverse=True)\r\n",
    "        m1.sort(reverse=True)\r\n",
    "        m2.sort(reverse=True)\r\n",
    "\r\n",
    "        s = sum(digits)\r\n",
    "        if s % 3 == 0:\r\n",
    "            # 如果全是零\r\n",
    "            if s == 0:\r\n",
    "                return \"0\"\r\n",
    "            return \"\".join(list(map(str, sorted(digits, reverse=True))))\r\n",
    "        if s % 3 == 1:\r\n",
    "            # 去除一个最小的 mod 3 == 1 的数\r\n",
    "            if len(m1):\r\n",
    "                m1.pop()\r\n",
    "            else :\r\n",
    "                m2.pop()\r\n",
    "                m2.pop()\r\n",
    "        else:  \r\n",
    "            # 去除一个最小的 mod 3 == 1 的数\r\n",
    "            if len(m2):\r\n",
    "                m2.pop()\r\n",
    "            else:\r\n",
    "                m1.pop()\r\n",
    "                m1.pop()\r\n",
    "        m = m0 + m1 + m2\r\n",
    "        m.sort(reverse=True)\r\n",
    "        if len(m) == 0:\r\n",
    "            return \"\"\r\n",
    "        if sum(m) == 0:\r\n",
    "            return \"0\"\r\n",
    "        return  \"\".join(list(map(str, m)))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
